# 2 Java solutions, recursion way & DP way, beat 98%

1. Recusion way:

Time Complexity: O(x^x), where x is the number of operators, which is at most n/2 -1. (n is the length of input string.)
(If I'm wrong, please tell me. Thank you!)

``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
return recursion(input);
}

private List<Integer> recursion(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 str_left = input.substring(0, i);
String str_right = input.substring(i+1);
List<Integer> res_left = recursion(str_left);
List<Integer> res_right = recursion(str_right);
for(int left_val : res_left){
for(int right_val : res_right){
if(c=='+'){
} else if(c=='-'){
} else {
}
}
}
}
}
return res;
}
}
``````
1. DP way:

Time Complexity: O(x^2 * y), where x is the number of operators, which is at most n/2 -1, and y is the size of output list.
(If I'm wrong, please tell me. Thank you!)

``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
final int N = input.length();
List<Integer>[][] dp = new ArrayList[N][N];
return recursion(input, 0, N-1, dp);
}

private List<Integer> recursion(String input, int start, int end, List<Integer>[][] dp) {
if(dp[start][end]!=null) return dp[start][end];
List<Integer> res = new ArrayList<>();
for(int i=start; i<=end; i++){
char c = input.charAt(i);
if(c=='+'||c=='-'||c=='*'){
List<Integer> res_left = recursion(input, start, i-1, dp);
List<Integer> res_right = recursion(input, i+1, end, dp);
for(int left_val : res_left){
for(int right_val : res_right){
if(c=='+'){
} else if(c=='-'){
} else {
}
}
}
}
}