Different Ways to Add Parentheses
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
|
HashMap<String, List<Integer>> map = new HashMap<>(); public List<Integer> (String input) { if (map.containsKey(input)) return map.get(input); List<Integer> ans = new ArrayList<>(); if (input == null || input.length() == 0) return ans; for (int i = 0; i < input.length(); ++i) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '*') { List<Integer> left = diffWaysToCompute(input.substring(0, i)); List<Integer> right = diffWaysToCompute(input.substring(i + 1)); for (int x : left) { for (int y : right) { int tmp = 0; switch(c) { case '+': tmp = x + y; break; case '-': tmp = x - y; break; case '*': tmp = x * y; break; default: break; } ans.add(tmp); } } } } if (ans.size() == 0) ans.add(Integer.parseInt(input)); map.put(input, ans); return ans; }
|
近期评论