DifferentWaysToAddParentheses [source code]
public class DifferentWaysToAddParentheses {
static
/******************************************************************************/
class Solution {
Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
if (map.containsKey(input))
return map.get(input);
List<Integer> res = new ArrayList<>();
char[] chs = input.toCharArray();
for (int i = 0; i < chs.length; i++) {
if (!Character.isDigit(chs[i])) {
String op1 = input.substring(0, i), op2 = input.substring(i + 1);
List<Integer> res1 = diffWaysToCompute(op1), res2 = diffWaysToCompute(op2);
if (chs[i] == '+') {
for (int j : res1)
for (int k : res2)
res.add(j + k);
} else if (chs[i] == '*') {
for (int j : res1)
for (int k : res2)
res.add(j * k);
} else { // '-'
for (int j : res1)
for (int k : res2)
res.add(j - k);
}
}
}
if (res.size() == 0)
res.add(Integer.parseInt(input));
map.put(input, res);
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
DifferentWaysToAddParentheses.Solution tester = new DifferentWaysToAddParentheses.Solution();
}
}
看到题目第一时间感觉还是有点思路的, 加上tag上面给了一个divide&conquer, 这个其实就是一个加法拆分思路的题目; 当然虽然有一个大概的思路, 真正代码写出来感觉并不是那么的trivial, 就连第一步的这个parse, 好像都要好好思考一下;
仔细想了一下, 这个题目其实不是一个加法拆分的思路, 这个题目的问题要更复杂一些; 这里的这个问题更像是给你一个serialization, 然后让你de-serialize一个tree出来, 不对, 不是一个, 是all; 这个可能就有点复杂了; 另外parse的方案还没有想好, 不过先不管, 应该不难想; parse有很多种方案, 我有预感, 我们最后可能不得不配合这后面的核心算法的思路(也就是deserialize的部分)来选择一个合适的parse方案, 所以暂时先不管这个;
刚开始盯着eg2看了半天, 根本看不出所以然; 事实上, 人逻辑的发现, 一定要动笔! 不要指望自己看看这里的这个trace就有结果了; 动了一下笔之后, 画了画第二个例子, 感觉思路立刻就清晰很多;
一个小细节, 这里是不需要remove duplicate的, 对应的, API里面给的最后的返回值也是list而不是set, 合情合理;
看起来好像很难写的一个题目, 最后居然时间限制以内写完了, 很开心, 速度是7ms (49%), 考虑波动的话, 其实速度还可以了;
core algorithm first
我决定不要上来就先考虑parse的决定是对的, 因为最后发现, 根本不用把string 给parse开来(事实上, 我一开始不想parse的一个重要原因就是因为感觉parse了之后这个divide的过程不是很好操作); 当我动笔, 找到人逻辑之后, 我发现每一个level要做的其实就是找到一个作为separator的operator就行了, 至于这个operator两头的东西, 直接两个substring丢下去就可以了, 根本不需要parse;
另外不写helper, 直接讲string作为recursion的参数, 使得我们最终可以加上memo的优化, 这个是很容易想到的; 这里的recursion还有一个问题就是考虑好base case, 其实很好处理, 因为这个算法我是先思考recursive call(root level recursion)部分, 然后思考base case的, 所以思考过程可能有点不熟悉, 不过其实是一样的, 你想好, 你没一个level做的是什么工作就行了: 找一个separator: 那么什么时候可以做到没有办法找到任何一个其他的separator? 这个时候的string其实就是一个数字. 知道了base case是什么之后, 下面就是思考怎么处理这个base case; 如果直接要提前单独判断一个string是否全都是数字还是很麻烦的, 更好的办法就是直接先还是正常走, 如果走完之后发现res没有被add任何的东西, 那么说明没有碰到任何的operator, 那么这个时候一个parseInt就行了;
另外, 我这里故意把判断operator的部分放到了组合答案的部分的上面, 我个人感觉, 虽然代码看起来累赘了一些, 但是对于一个iteration, 这个operator其实是固定的, 我们对左右两边返回上来的两个list里面的每一个pair都重新进行一次operator的判断, 还是有点浪费了; 可惜最后我的算法速度却并不怎么快, 很奇怪;
最后知道问题出在哪里了, 我memo没有写完整:
map.put(input, res);
这一句忘记写了; 写完之后速度就上去了: 3(88); 这个应该算是最优解了;
discussion大部分的解法都是跟我的这个解法意思是一样的, 这里有一个人的看法:
@ragepyre said in C++ 4ms Recursive & DP solution with brief explanation:
Nice solution, I have nearly the same code.
The key idea for this solution is: each operator in this string could be the last operator to be operated. We just iterator over all these cases
这个思路整体是对的, 我们最后build出来的(underlying the recursion/dfs)的就是一个tree机构, 而没一层我们可以认为, 每一个internal node就代表一个operator(所以这个题目如果你直接能够先把tree traversal画出来或许也有帮助, 只不过我感觉tree traversal在这里更多的还是一个验证思路正确性的辅助工具, 而不是能够帮助你想到这个思路的工具); 这个人这里的解释其实着眼的就是每次提取出来一个最高level的operator, 也就是提取出当前tree的root(root一定程度上也可以看成是一个internal node);
另外一个人的观点:
Nice solution. The code is clean.
Two more points. First, using a map to memorize the results of previous solved problems can help.
Second, instead of checking the size of list in the end, I prefer to check if the input is digit or not. Which make the code more robust.
也就是base case怎么处理; 我其实不是很认同他的看法, 如果每一个string上来就要先check一下digit, 那么就多出来很多这个API的调用; 而且他这里这个所谓的robust也不知道从何说起;
我之前的一个刻板印象就是认为这种string题目, 要是想要利用memo, 那么就肯定不能做成char array来处理; 但是其实之前做过一个题目当时就是已经证明这个思路是错的了; 我之所以形成这个错误印象的原因是因为我潜意识里面还是认为, 一个subarray, 就是用一个subarray本身这个变量/指针来表示和传递; 但是在recursion设计的时候, 我们对于subarray的表示往往更多的是用(array, lo, hi)这样的一个tuple, 也就是index来表示的; 理解这一点之后, 就知道其实用char array的思路也是完全可以实现memo的, 而且这样的memo往往还不需要用HashMap, 而是直接一个matrix/array就可以解决, 速度更快;
@SylvanasWindrunner said in Java recursive (9ms) and dp (4ms) solution:
I think it's more efficient to pre-parse the string because String.substring() is costly. I store the parsed string in a list, for example, if the string is 1+2+3+4, then the list will contain:
"1", "+", "2", "+", "3", "+", "4"Personally I feel this is also more convenient because all integers occurs at even indices (0, 2, 4, 6) and all operators are at odd indices (1, 3, 5).
Then the problem is very similar to "Unique Binary Search Trees II". For each operator in the list, we compute all possible results for entries to the left of that operator, which is
List<Integer> left, and also all possible results for entries to the right of that operator, namelyList<Integer> right, and combine the results. It can be achieved by recursion or more efficiently by dp.Recursion:
public List<Integer> diffWaysToCompute(String input) {
List<Integer> result=new ArrayList<>();
if(input==null||input.length()==0) return result;
List<String> ops=new ArrayList<>();
for(int i=0; i<input.length(); i++){
int j=i;
while(j<input.length()&&Character.isDigit(input.charAt(j)))
j++;
String num=input.substring(i, j);
ops.add(num);
if(j!=input.length()) ops.add(input.substring(j, j+1));
i=j;
}
result=compute(ops, 0, ops.size()-1);
return result;
}
private List<Integer> compute(List<String> ops, int lo, int hi){
List<Integer> result=new ArrayList<>();
if(lo==hi){
Integer num=Integer.valueOf(ops.get(lo));
result.add(num);
return result;
}
for(int i=lo+1; i<=hi-1; i=i+2){
String operator=ops.get(i);
List<Integer> left=compute(ops,lo, i-1), right=compute(ops, i+1, hi);
for(int leftNum:left)
for(int rightNum: right){
if(operator.equals("+"))
result.add(leftNum+rightNum);
else if(operator.equals("-"))
result.add(leftNum-rightNum);
else
result.add(leftNum*rightNum);
}
}
return result;
}
这个parse我刚开始看的时候感觉可能不对, 如果i的位置就是一个operator怎么办, 但是想了想之后, 发现他这里是把一个number+operator的组合的一个pair作为一个整体来处理的; 最后只要再单独加上一个收尾处理最后一个数字就行了; 这个不是一个最general的分段算法, 而是一个根据这个问题的input的特性设计的parse;
另外, 这里他的subproblem的表示, 除了index之外, 大的结构用list而不是array, 也是可以的, list也支持index操作;
And DP, where dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive) in the list.
public List<Integer> diffWaysToCompute(String input) {
List<Integer> result=new ArrayList<>();
if(input==null||input.length()==0) return result;
List<String> ops=new ArrayList<>();
for(int i=0; i<input.length(); i++){
int j=i;
while(j<input.length()&&Character.isDigit(input.charAt(j)))
j++;
ops.add(input.substring(i, j));
if(j!=input.length()) ops.add(input.substring(j, j+1));
i=j;
}
int N=(ops.size()+1)/2; //num of integers
ArrayList<Integer>[][] dp=(ArrayList<Integer>[][]) new ArrayList[N][N];
for(int d=0; d<N; d++){
if(d==0){
for(int i=0; i<N; i++){
dp[i][i]=new ArrayList<>();
dp[i][i].add(Integer.valueOf(ops.get(i*2)));
}
continue;
}
for(int i=0; i<N-d; i++){
dp[i][i+d]=new ArrayList<>();
for(int j=i; j<i+d; j++){
ArrayList<Integer> left=dp[i][j], right=dp[j+1][i+d];
String operator=ops.get(j*2+1);
for(int leftNum:left)
for(int rightNum:right){
if(operator.equals("+"))
dp[i][i+d].add(leftNum+rightNum);
else if(operator.equals("-"))
dp[i][i+d].add(leftNum-rightNum);
else
dp[i][i+d].add(leftNum*rightNum);
}
}
}
}
return dp[0][N-1];
}
Bottom-Up的DP解法, 总体还是跟上面的解法思路差不多的;
需要注意的就是, 这里的表格的大小是多少? 他这里表格的大小使用的是数字的个数; 这个数字的个数怎么计算? (len + 1) / 2, 这个其实也是碰到过的了; 自己举例子就行了, 是mid的ceiling;
这里的表格的维度是0-based, 所以size没有必要+1; 另外, 这里的这些index, 是用来delimit一个subarray的, 这种时候还有一个问题要确定一下: 右端点是否是inclusive? 这里采用的方法是inclusive, 也就是是一个闭区间;
这个DP算法还是有一些subtlety的, 首先, 这里说了parse, 有没有想过为什么他最后parse出来的结果是这样存储的? 我一开始自己想parse的时候的想法是, 数字和operator分别放在两个array/list里面; 但是他这里直接就是全部都塞到一个list里面去, 最后取出来的时候, 完全就是依靠index的计算来进行一个跳子的取数; 两种方法哪个好还不好说, 但是他这个方法最后做起来其实也不是很麻烦;
另外一个就是dinitz在上课的时候说过的一个问题, Bottom-Up的时候, 填表的顺序非常重要, 脑子里要有一个dependency的概念;
之前好像见过一次关于subarray的DP问题, 当时最后填表的时候就有点麻烦, 但是当时忘记总结了; 这里就又见到一次, 可以看到, 这里填表的过程实际上是有三个循环的, 这个是合理的, 因为就算是Top-Down的方法, 最后写出来复杂度也是(N^3, fanning是N);
只不过Top-Down的时候, 你根本不需要考虑填表的顺序, 直接用的时候去查, 查不到就填就行了; 但是Bottom-Up的时候, 就要思考一下顺序; 这里的顺序是由外到内:
- subarray的长度: d: 从小到大;
- subarray的起点: i: 从左到右;
- subarray的终点是不需要确定的! 固定就是i+d(again, 闭区间);
- j其实是在subarray内部完成一个fanning的过程;
这个Bottom-Up写的有点像Top-Down, 我记得当时第一次写subarray DP的时候, 好像不是这个顺序, 但是也想不起来这里还有什么更好的顺序;
在填表的时候, 除了思考顺序, 在写代码的时候, 脑子里始终要提醒自己, 我现在正在填的是那个entry, 比如这里, 在第一层循环以内, 你记得自己要填的就是[i][i+d]就行了; 而j只是用来辅助填这个entry的工具;
另外, 关于这个算法的复杂度, 粗糙一点的算法当然是N^3: N^2个substring, 然后每一个substring需要走一个length的fanning, WorstCase是N; 但是这个是不tight的; 比如N是5, 那么我们最后计算的应该是一个15+42+33+24+5*1, 看起来应该是一个有规律的计算, 但是好像也不知道应该用什么去算;
基本没有其他的解法了;
Problem Description
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Difficulty:Medium
Total Accepted:46.2K
Total Submissions:104.7K
Contributor: LeetCode
Related Topics
divide and conquer
Similar Questions
Unique Binary Search Trees II Basic Calculator Expression Add Operators