# A recursive Java solution (284 ms)

• ``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
for (int i=0; i<input.length(); i++) {
if (input.charAt(i) == '-' ||
input.charAt(i) == '*' ||
input.charAt(i) == '+' ) {
String part1 = input.substring(0, i);
String part2 = input.substring(i+1);
List<Integer> part1Ret = diffWaysToCompute(part1);
List<Integer> part2Ret = diffWaysToCompute(part2);
for (Integer p1 :   part1Ret) {
for (Integer p2 :   part2Ret) {
int c = 0;
switch (input.charAt(i)) {
case '+': c = p1+p2;
break;
case '-': c = p1-p2;
break;
case '*': c = p1*p2;
break;
}
}
}
}
}
if (ret.size() == 0) {
}
return ret;
}
}``````

• Hi, 2guotou. Your idea is really clever and easy to understand, as well as your code. I rewrite it in C++ (well, just like translation). Hope it is Ok :-)

``````class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> outputs;
int n = input.length();
for (int i = 0; i < n; i++) {
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
string left = input.substr(0, i);
string right = input.substr(i + 1, n - i - 1);
vector<int> lval = diffWaysToCompute(left);
vector<int> rval = diffWaysToCompute(right);
for (int l : lval) {
for (int r : rval) {
switch (input[i]) {
case '+':
outputs.push_back(l + r);
break;
case '-':
outputs.push_back(l - r);
break;
default:
outputs.push_back(l * r);
}
}
}
}
}
if (outputs.empty())
outputs.push_back(stoi(input));
return outputs;
}
};``````

• Did you reimplement stoi on purpose? And substr doesn't need the second parameter.

• Hi, Stefan. I almost did not realize `stoi`. About `substr`, I guess the expression for `right` need not have the second parameter, but the expression for `left` still needs. Is that right? BTW, I have updated my code.

• This post is deleted!

• it is just the Catalan number, in wiki

• This is a nice and clean solution. However, note that there are many overlapping sub-problems, dynamic programming should be a potential way to improve the performance.

• Using a map to memorize would be better.

• Hi, doesn't empty string break the code?

• I wish one day I should write a code like this on my own .

• this solution may calculate the same expression several times

• This is a brilliant solution except that may calculate the same expression several times when input is same.
I modify a little bit and use a HashMap to memorize results for an input

``````public class Solution {

Map<String, List<Integer>> map = new HashMap<>();

public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
String p1 = input.substring(0, i);
String p2 = input.substring(i + 1);
List<Integer> l1 = map.getOrDefault(p1, diffWaysToCompute(p1));
List<Integer> l2 = map.getOrDefault(p2, diffWaysToCompute(p2));
for (Integer i1 : l1) {
for (Integer i2 : l2) {
int r = 0;
switch (c) {
case '+':
r = i1 + i2;
break;
case '-':
r = i1 - i2;
break;
case '*':
r = i1 * i2;
break;
}
}
}
}
}
if (res.size() == 0) {
}
map.put(input, res);
return res;
}
}``````

• what's the time complexity for this??thanks

• Good solution! one minor suggestion: changing LinkedList to ArrayList will improve decrease the runtime significantly.

• @2guotou

Brilliant.
I think this can be optimized with memorization, to save some duplicate recursive calls.
After optimization, it is 3 ms.

Please find my optimization with Hashtable memorization below.

``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
return dfs(input, new HashMap<String, List<Integer>>());
}

private List<Integer> dfs(String input, Map<String, List<Integer>> map){
if(map.containsKey(input)) return map.get(input);

List<Integer> result = new ArrayList<>();
for(int i=0;i<input.length();i++){
char curChar = input.charAt(i);
if(curChar == '+' || curChar == '-' || curChar == '*'){
String leftPart = input.substring(0,i);
String rightPart = input.substring(i+1);
List<Integer> leftResult = dfs(leftPart, map);
List<Integer> rightResult = dfs(rightPart, map);
for(Integer left: leftResult){
for(Integer right: rightResult){
int curResult = 0;
switch (curChar){
case '+':
curResult = left + right;
break;
case '-':
curResult = left - right;
break;
case '*':
curResult = left * right;
break;
}
}
}
}
}

if(result.size() == 0){
}

map.put(input, result);
return result;
}
}

``````

• @1337c0d3r Sure and done

• @ran3 What would be the time complexity for the solution?

• @ran3 Good idea, the longer the string, the more time saved.

• So the time complexity would be O(n^3)?

• Very nice base case handle and the use of hashmap cache of sub-problem solution. Thanks for sharing!

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