BiruLyu
6/6/2017 - 11:49 PM

## 241. Different Ways to Add Parentheses(1st).java

``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if(c == '+' || c == '-' || c == '*') {
String left = input.substring(0, i);
String right = input.substring(i + 1);
List<Integer> leftValues = diffWaysToCompute(left);
List<Integer> rightValues = diffWaysToCompute(right);
for (int l : leftValues) {
for (int r : rightValues) {
if (c == '+') res.add(l + r);
else if (c == '-') res.add(l - r);
else if (c == '*') res.add(l * r);
}
}
}
}
return res;
}
}``````
``````public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> rst=new ArrayList<Integer>();
if(input==null || input.length()==0){
return rst;
}

HashMap<String,List<Integer>> map=new HashMap<String, List<Integer>>();
rst=diffWaysToCompute(input,map);
return rst;

}

public List<Integer> diffWaysToCompute(String input, HashMap<String,List<Integer>> map){
if(map.containsKey(input)){
return map.get(input);
}

List<Integer> list=new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
if(input.charAt(i)=='+' || input.charAt(i)=='-' || input.charAt(i)=='*'){
List<Integer> leftList=diffWaysToCompute(input.substring(0,i), map);
List<Integer> rightList=diffWaysToCompute(input.substring(i+1), map);

for(int leftn : leftList){
for(int rightn : rightList){
if(input.charAt(i)=='+'){
}else if(input.charAt(i)=='-'){
}else if(input.charAt(i)=='*'){
}
}
}
}
}

if(list.size()==0 && input.length()!=0){