# Java recursive solution with memorization

• ``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
//cache for memorization
HashMap<String,List<Integer>> cache = new HashMap<String,List<Integer>>();
return this.helper(input,cache);
}

List<Integer>helper(String s, HashMap<String,List<Integer>> cache) {
if (cache.get(s)!=null) {
return cache.get(s);
}
boolean expression = false;
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=0; i<s.length(); i++) {
if("+-*".indexOf(s.charAt(i))!=-1) {
List<Integer> left = helper(s.substring(0,i),cache);
List<Integer> right = helper(s.substring(i+1),cache);
for(Integer l: left) {
for(Integer r: right) {
}
}
expression = true;
}
}
if (!expression) {
}
cache.put(s, result);
return result;
}
int cal(int l, int r, char op) {
int result = 0;
switch (op) {
case '+': result= l+r; break;
case '-': result = l-r; break;
case '*': result= l*r; break;
default: break;
}
return result;
}
}
``````

We first split the string by operators and recursively calculate left and right side, then combine the result. The only improvement is to use memorization to cache previously calculated expressions.

• "+-*".indexOf(s.charAt(i))!=-1 This is clever.

• learn a new tip today.

• Is the complexity O(n^2)? (n is the number of numbers in the string)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.