往上加运算符也好，加括号也好，删除括号也好，最稳妥的方式都是 带 StringBuilder 从头扫的 DFS + Backtracking.
在没有任何优先级后顾之忧的情况下，可以以操作符为分界线，Divide & Conquer. 否则得存每个 subproblem 的前后缀用于做 join.
有乘法优先级顾虑时，需要在 dfs 参数里传上一次操作的值，用于恢复和重新计算；连续多个乘法可以自动叠加。
在只有一种括号的情况下，维护 left / right count 就可以 one-pass 知道到底有几个 left / right 括号没正确匹配
Dijkstra 的 Shunting-Yard 算法是生成 RPN 的大杀器，也是 calculator 类问题的通解。
先说一个自己的做法，写的是搜索，对于每一个 input string ，我们扫描并建立两个 list; 一个是 operands，一个是 operators. 每次 dfs 的时候挑一对数字和一个操作符，计算，修改 list 做 dfs，返回之后再把 list 改回来。
过了 15/25 个 test case 之后卡在了 "2*3-4*5" 上面，原因是多了一个额外的 -14，因为两个 subproblem 加括号的方式是一样的，顺序不同而已。
所以暴力搜索的问题在于，如果前面和后面加括号的方式是一样的，需要额外手段来判断 “重复” 。
而DFS 中想 cache 一个 List<>，远远不如 String 方便。
如果实在追求暴力到底，就干脆对每一个状态都搞序列化，记录当前的 operands & operators ，遇到重复的状态就直接返回了。
因此为了避免 dfs + backtracking 可能遇到的 overlap subproblem 返回多个结果的问题，可以先直接 divide & conquer，因为这个搜索结构是树状的，天生的 disjoint.
根据这个思想，我们可以以“操作符”为分隔，借鉴编译器和 reverse polish notation 中的 "expression tree" 来进行计算，结构如下：
这样左右子树都进行的完美的分隔，而且应为 input 为 string ，也非常容易对子问题进行记忆化搜索。
Divide & Conquer, 8ms，超过 41.50%.
Copy public class Solution {
public List < Integer > diffWaysToCompute ( String input) {
List < Integer > rst = new ArrayList <>();
for ( int i = 0 ; i < input . length (); i ++ ){
if ( ! Character . isDigit ( input . charAt (i))){
char operator = input . charAt (i);
List < Integer > left = diffWaysToCompute( input . substring( 0 , i)) ;
List < Integer > right = diffWaysToCompute( input . substring(i + 1 )) ;
for ( int num1 : left){
for ( int num2 : right){
if (operator == '+' ) rst . add (num1 + num2);
if (operator == '-' ) rst . add (num1 - num2);
if (operator == '*' ) rst . add (num1 * num2);
}
}
}
}
if ( rst . size () == 0 ) rst . add ( Integer . parseInt (input));
return rst;
}
} 带记忆化搜索，3ms，超过 91.61%
Copy public class Solution {
public List < Integer > diffWaysToCompute ( String input) {
return helper(input , new HashMap < String , List < Integer >>()) ;
}
private List < Integer > helper ( String str , HashMap < String , List < Integer >> map){
if ( map . containsKey (str)) return map . get (str);
List < Integer > list = new ArrayList <>();
for ( int i = 0 ; i < str . length (); i ++ ){
char chr = str . charAt (i);
if ( ! Character . isDigit (chr)){
List < Integer > leftList = helper( str . substring( 0 , i) , map) ;
List < Integer > rightList = helper( str . substring(i + 1 ) , map) ;
for ( int leftNum : leftList){
for ( int rightNum : rightList){
if (chr == '+' ) list . add (leftNum + rightNum);
if (chr == '-' ) list . add (leftNum - rightNum);
if (chr == '*' ) list . add (leftNum * rightNum);
}
}
}
}
if ( list . size () == 0 ) list . add ( Integer . parseInt (str));
map . put (str , list);
return list;
}
} 首先最容易想到的是 naive 的 O(n^2) 解法，即以每一个 '(' 为起点向右扫，看到 '(' count ++，看到 ')' count -- ，什么时候 count = 0 代表当前 substring 是有效的，count 为负则直接 break.
注意这招只在只有一种括号的时候有效，不能用来做 "Valid Parentheses"，会在 "([)]" 这种 test case 上挂掉。
显然，因为时间复杂度过高这么写不能 AC，因为重复扫描实在太多了。
Copy public class Solution {
public int longestValidParentheses ( String s) {
if (s == null || s . length () == 0 ) return 0 ;
int n = s . length ();
int max = 0 ;
for ( int i = 0 ; i < n; i ++ ){
char chr = s . charAt (i);
if (chr == '(' ){
int count = 1 ;
int ptr = i + 1 ;
while (ptr < n){
if ( s . charAt (ptr) == '(' ) count ++ ;
if ( s . charAt (ptr) == ')' ) count -- ;
if (count == 0 ) max = Math . max (max , ptr - i + 1 );
if (count < 0 ) break ;
ptr ++ ;
}
}
}
return max;
}
} 仔细思考一下我们如何定义 "Valid Parenthese"，还有他们都长什么样。
Valid Parenthese 只有可能是这两种情况；
以一对括号为 "kernel" ，向外扩散的，如 ((()))
多个 "kernel" 扩张出现，相互连续的，如 (())()(())
参考了 LC 论坛的一种解法，非常巧妙，利用了这样的一个隐藏性质：
用 Stack 做常规括号匹配，字符串扫描完毕之后，还存留在 Stack 中的 index 都是无法匹配的字符。
如果字符串正常从左向右扫的话，这个 Stack 中的元素 index 还是排好序的，元素 index 之间的 gap，就代表着可以匹配的括号。
同时要注意考虑字符串最两端作为起点和终点的可能性，用最右端做初始化，用最左端做收尾。
于是就有了下面这个 O(n) 的代码，空间复杂度为 O(n / 2);
Copy public class Solution {
public int longestValidParentheses ( String s) {
if (s == null || s . length () == 0 ) return 0 ;
Stack < Integer > stack = new Stack <>();
for ( int i = 0 ; i < s . length (); i ++ ){
if ( s . charAt (i) == '(' ) stack . push (i);
else if ( ! stack . isEmpty () && s . charAt ( stack . peek ()) == '(' ) stack . pop ();
else stack . push (i);
}
// Whole string is matched
//if(stack.isEmpty()) return s.length();
int rightEnd = s . length ();
int max = 0 ;
while ( ! stack . isEmpty ()){
int cur = stack . pop ();
max = Math . max (max , rightEnd - cur - 1 );
rightEnd = cur;
}
max = Math . max (max , rightEnd);
return max;
}
} 另一种解法是用 DP，空间占用大一倍，但是速度快，思路上非常接近于 Palindrome Partitioning.
dp[i] = 以 i 结尾的括号的最长 valid parenthese 长度
先读 dp[i - 1] 的长度，然后根据长度找到最左面的目标位置 leftPos，看看是不是 '('，如果是，就可以 dp[i] = dp[i - 1] + 2 了，代表可以连续构造；
另一种情况是多个独立的括号序列相邻，所以每次如果当前位置可以构造括号，要再找一下 dp[leftPos - 1] 的长度，把相邻序列串起来。
速度超过85.05% ~
Copy public class Solution {
public int longestValidParentheses ( String s) {
if (s == null || s . length () == 0 ) return 0 ;
int n = s . length ();
int [] dp = new int [n]; // dp[i] = Maximum valid parentheses length ends with i
dp[ 0 ] = 0 ;
int max = 0 ;
for ( int i = 1 ; i < s . length (); i ++ ){
if ( s . charAt (i) == ')' ){
int len = dp[i - 1 ];
int leftPos = i - len - 1 ;
if (leftPos >= 0 && s . charAt (leftPos) == '(' ) {
dp[i] = dp[i - 1 ] + 2 ;
if (leftPos - 1 >= 0 ) dp[i] += dp[leftPos - 1 ];
} else {
dp[i] = 0 ;
}
max = Math . max (max , dp[i]);
}
}
return max;
}
} (FB) 简化版，Remove Invalid Parenthese
http://www.1point3acres.com/bbs/thread-192179-1-1.html
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"
简单说，就是在尽量保留有效括号的情况下，返回任意一种正确结果。
在只有一种括号的时候，是可以扫一遍通过 +/- 来找出非法括号的，不过以一个方向定义的 +/- 只能找出一种，需要两个方向都扫一遍。
"(" 为正 , ")" 为负 ，从左向右可以找到非法的 ')'
")" 为正，"(" 为负，从右向左可以找到非法的 '('
后面的就非常 trivial 了。
Copy private static String removeInvalid( String str) {
char [] chrArr = str . toCharArray ();
int val = 0 ;
for ( int i = 0 ; i < chrArr . length ; i ++ ){
if (chrArr[i] == '(' ) val ++ ;
else if (chrArr[i] == ')' ) val -- ;
if (val < 0 ) {
chrArr[i] = '#' ;
val = 0 ;
}
}
val = 0 ;
for ( int i = chrArr . length - 1 ; i >= 0 ; i -- ){
if (chrArr[i] == ')' ) val ++ ;
else if (chrArr[i] == '(' ) val -- ;
if (val < 0 ){
chrArr[i] = '#' ;
val = 0 ;
}
}
StringBuilder sb = new StringBuilder() ;
for ( int i = 0 ; i < chrArr . length ; i ++ ){
if (chrArr[i] != '#' ) sb . append (chrArr[i]);
}
return sb . toString ();
}
public static void main( String [] args) {
String [] testcases = new String []{ "()()()()((()()())()(" ,
"()AD(S)A()W)(S))()ASD()" ,
"))ASDAS()()()Q(((())QWE)()" ,
"S()((A)()D))W)Q())(EQ())()W(" ,
"))ASD)QW(()S(Q)(WE)(Q()(AS)D(" };
for ( int i = 0 ; i < testcases . length ; i ++ ){
System . out . println ( "Input : " + testcases[i]);
System . out . println ( "Output : " + removeInvalid(testcases[i]) );
System . out . println ();
}
} 这题的结构就和 Different ways to add parenthese 不一样，括号之间的相对位置是非常重要的，而且有连续性，不能像那题一样直接在操作符上建一个 expression tree 出来，divide & conquer.
首先继承上一题 Stack 的经验，我们很容易可以知道需要的最少 edit 次数，以及 invalid 字符位置：跑一遍算法，看 Stack 里剩几个元素，分别在哪就行了。
只有一个非法括号的情况：
( ( ) ) ( ) '(' ( ( ) ) ( )
可以发现对于 '(' ，只能向右删下一个 '('，相邻的 '(' 是重复解
( ) ( ( ) ) ')' ( ) ( ( ) )
同理，')' 只能往左边找')'，相邻 ')' 为重复解。
有两个非法括号的情况：
( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )
( ) ( ( ) ) ( ) ( ( ) ) ( )
( ) ( ( ) ) ')' ( ) '(' ( ( ) ) ( )
可以发现 ')' 有两个可能的位置，'(' 有两个可能的位置，于是是 4 种组合。
于是这题就变成了一个搜索问题~
问题1：既然在反复在字符串上进行修改，如何还能保证 List<> 里面的非法字符位置还是正确的？
问题2：动态修改的 string ，动态变化的 index，要处理很多细节保证他们的 match.
觉得顺着这个思路越想细节越多。。于是参考了下论坛的 DFS 思路，在所有 DFS 解法中，我最喜欢这个，非常简洁易懂，而且不依赖什么 trick，便于和面试官交流。
先扫一遍原 string ，记录下需要移除的左括号数量和右括号数量，保证最后的解最优；
于是开始 DFS，对于每一个新的字符，我们都有两个选择：'留' 或者 '不留'，就像二叉树的分叉一样，留下了 dfs + backtracking 的空间。
于是当我们针对各种情况进行 dfs 的时候，我们一定可以考虑到所有可能的有效 path，接下来需要定义什么是 “有效 path”
base case 是左右括号和开括号数量都为零，并且 index 读取完了所有字符，则把结果添加进去；
如果在任何时刻，左右括号和开括号的数量为负，我们都可以直接剪枝返回。
这种解法的主要优点是好理解，空间上因为只用了一个 StringBuilder 非常经济，相比 BFS 速度和空间上都优异很多。如果说进一步优化的空间在哪，那就是对于 “重复状态” 的缓存与记忆化搜素还有提高的空间。
于是很 naive 的尝试了下加入 Set<> 来记录已经访问过的 StringBuilder 状态试图剪枝，然而很容易就出了 “没有任何返回结果” 的 bug ，其原因是，这个 dfs + backtracking 的代码本来就是在一个神似 binary tree 的结构上做一个 dfs 穷举而已，并不是 top-down recursion 那种子问题覆盖的结构，所以不适合用记忆化搜索解决。非要用的话至少 dfs 的返回类型就不能是 void ，至少也得是个 List<> 或者 Set<> 之类的 “子问题结果” 嘛。
Copy public class Solution {
public List < String > removeInvalidParentheses ( String s) {
Set < String > set = new HashSet <>();
int leftCount = 0 ;
int rightCount = 0 ;
int openCount = 0 ;
for ( int i = 0 ; i < s . length (); i ++ ){
if ( s . charAt (i) == '(' ) leftCount ++ ;
if ( s . charAt (i) == ')' ){
if (leftCount > 0 ) leftCount -- ;
else rightCount ++ ;
}
}
dfs(set , s , 0 , leftCount , rightCount , openCount , new StringBuilder()) ;
return new ArrayList < String >(set);
}
private void dfs ( Set < String > set , String str , int index , int leftCount ,
int rightCount , int openCount , StringBuilder sb){
if (index == str . length () && leftCount == 0 && rightCount == 0 && openCount == 0 ){
set . add ( sb . toString ());
return ;
}
if (index == str . length () || leftCount < 0 || rightCount < 0 || openCount < 0 ) return ;
char chr = str . charAt (index);
int len = sb . length ();
if (chr == '(' ){
// Remove current '('
dfs(set , str , index + 1 , leftCount - 1 , rightCount , openCount , sb) ;
// Keep current '('
dfs(set , str , index + 1 , leftCount , rightCount , openCount + 1 , sb . append(chr)) ;
} else if (chr == ')' ){
// Remove current ')'
dfs(set , str , index + 1 , leftCount , rightCount - 1 , openCount , sb) ;
// Keep current ')'
dfs(set , str , index + 1 , leftCount , rightCount , openCount - 1 , sb . append(chr)) ;
} else {
// Just keep the character
dfs(set , str , index + 1 , leftCount , rightCount , openCount , sb . append(chr)) ;
}
// Back-tracking
sb . setLength (len);
}
} 参考论坛思路的一个 BFS 写法，速度很慢只能超过 14%，搞的有点像 word ladder 了。。。 不过另一个好处是，既然这么高的时间复杂度都能过，我那个 dfs 的解法也不用太追求完美，这样 index offset 的问题更好解决，遇到个新 string 直接重扫就好了。
Copy public List< String > removeInvalidParentheses( String s) {
List < String > rst = new ArrayList <>();
if ( isValid(s) ){
rst . add (s);
return rst;
}
Set < String > visited = new HashSet <>();
Queue < String > queue = new LinkedList <>();
boolean isFound = false ;
visited . add (s);
queue . offer (s);
while ( ! queue . isEmpty () && ! isFound ){
int size = queue . size ();
for ( int i = 0 ; i < size; i ++ ){
String str = queue . poll ();
for ( int pos = 0 ; pos < str . length (); pos ++ ){
StringBuilder sb = new StringBuilder(str) ;
sb . deleteCharAt (pos);
String next = sb . toString ();
if ( visited . contains (next)) continue ;
if ( isValid(next) ){
isFound = true ;
rst . add (next);
} else {
queue . offer (next);
}
visited . add (next);
}
}
}
return rst;
}
private boolean isValid( String s) {
if (s == null || s . length () == 0 ) return true ;
int count = 0 ;
for ( int i = 0 ; i < s . length (); i ++ ){
if ( s . charAt (i) == '(' ) count ++ ;
if ( s . charAt (i) == ')' ) count -- ;
if (count < 0 ) return false ;
}
return (count == 0 );
} num = "105", target = 5;
返回 ["10-5", "1x0+5", "1+0x5", "1x05", "1-0x5"] 是错的
在 Different ways to add parentheses 里，这么干没有任何问题，因为默认是加括号的，左右子树可以完全分离，单独求值。
而这题里，用 divide & conquer 无可避免地遇到符号优先级问题。于是看了一圈 LC 论坛，大家的做法其实都是 DFS + backtracking ..
这题非要用 divide & conquer 也不是不行，但是极其麻烦，如图所示：
对于每一个节点，我们需要考虑其左子树的 String, value，还有抹去最后一步运算的 String 与 value .. 对于右子树，我们还需要其抹去第一步运算的 String 与 value 才能正确做 join.
所以说，珍爱生命，有乘法就远离 divide & conquer 吧。
一个思路不错的帖子 ，这种做法就不用考虑 join了，只要做乘法的时候看它的前一个元素就行；
流程：
dfs 函数中存 "左面表达式的当前值" 和 "上一步操作的结果" (用于处理优先级)
参数都用 Long，防止溢出，毕竟 String 可能是个大数
如果 start 位置是 0 而且当前循环的 index 还是 0，直接 return，因为一轮循环只能取一次 0；
start == 0 的时候，直接考虑所有可能的起始数字扔进去，同时更新 cumuVal 和 prevVal;
除此之外，依次遍历所有可能的 curVal parse，按三种不同的可能操作做 dfs + backtracking;
加法：直接算，prevVal 参数传 curVal，代表上一步是加法；
减法：直接算，prevVal 参数传 -curVal，代表上一步是减法；
乘法：要先减去 prevVal 抹去上一步的计算，然后加上 prevVal curVal 代表当前值；同时传的 preVal 参数也等于 prevVal curVal.
乘法操作这种处理方式，在遇到连续乘法的时候可以看到是叠加的；但是前一步操作如果不是乘法，则可以优先计算乘法操作。
10-5-2x6 ，遇到乘法之前是 cumuVal = 3, preVal = -2; 新一轮 dfs 时 curVal = 6, 先退回前一步操作 - prevVal，得到 5，其实就是之前 (10 - 5) 的结果，然后加上当前结果 (-2 x 5)，prevVal 设成 -10 传递过去即可。
Copy public class Solution {
public List < String > addOperators ( String num , int target) {
List < String > rst = new ArrayList <>();
dfs(rst , new StringBuilder() , num , target , 0 , 0 , 0 ) ;
return rst;
}
private void dfs(List<String> rst, StringBuilder sb, String num, int target, int startPos, long cumuVal, long prevVal){
if (startPos == num.length() && cumuVal == target){
rst . add ( sb . toString ());
return ;
}
for ( int i = startPos; i < num . length (); i ++){
// We can pick one zero to start with; but not multiple
if ( num . charAt (startPos) == '0' && i != startPos) return ;
int len = sb . length ();
String curStr = num . substring (startPos , i + 1 );
long curVal = Long . parseLong (curStr);
if (startPos == 0 ){
dfs(rst , sb . append(curVal) , num , target , i + 1 , curVal , curVal) ;
sb . setLength (len);
} else {
dfs(rst , sb . append( "+" + curStr) , num , target , i + 1 , cumuVal + curVal , curVal) ;
sb . setLength (len);
dfs(rst , sb . append( "-" + curStr) , num , target , i + 1 , cumuVal - curVal , - curVal) ;
sb . setLength (len);
dfs(rst, sb.append("*" + curStr), num, target, i + 1, cumuVal - prevVal + prevVal * curVal, prevVal * curVal);
sb . setLength (len);
}
}
}
} Input: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
数字可能是多数位的，也可能是0，不能 assume 都是一位数；
复现了一下 Dijkstra 的 shunting yard algorithm，因为只有 “+” 和 “-” ，运算符优先级上要简单一些。在这个代码基础上扩展任何新的运算符都很容易，加个判断函数就行了。
建个 StringBuilder 存输出的 RPN，一个 Stack 存运算符；
如果看到数字，直接添加到 StringBuilder 中；
如果看到 ")"，把 Stack 上的所有运算符 pop 出来添加到 StringBuilder，直到遇见 "(" 为止；
如果看到运算符，把 Stack 上所有 "大于等于当前运算符优先级" 的 pop 出来加到 StringBuilder，最后把自己放入 Stack，此时要么 Stack 为空，要么 Stack.peek() 的优先级比当前运算符小。
Copy public class Solution {
public int calculate ( String s) {
// "(10+( 14+25+2)-0)+(0+18)"
// multiple digits;
// number zero;
// have spaces;
return solveRPN(getRPN(s)) ;
}
// "123 \s 23 \s + \s 45 \s - \s 44 ..."
private String getRPN ( String s){
StringBuilder sb = new StringBuilder() ;
Stack < Character > stack = new Stack <>();
for ( int i = 0 ; i < s . length (); i ++ ){
char chr = s . charAt (i);
if (chr == ' ' ) continue ;
if ( Character . isDigit (chr)){
sb . append (chr);
} else {
sb . append ( ' ' );
if (chr == '(' ){
stack . push (chr);
} else if (chr == ')' ){
while ( ! stack . isEmpty () && stack . peek () != '(' ){
sb . append ( stack . pop ());
sb . append ( ' ' );
}
stack . pop ();
} else {
// is "+" or "-" operator with same precedence level
while ( ! stack . isEmpty () && stack . peek () != '(' ){
sb . append ( stack . pop ());
sb . append ( ' ' );
}
stack . push (chr);
}
}
}
while ( ! stack . isEmpty ()){
sb . append ( ' ' );
sb . append ( stack . pop ());
}
return sb . toString ();
}
private int solveRPN ( String s){
String [] strs = s . split ( " " );
Stack < Integer > stack = new Stack <>();
for ( String str : strs){
if ( str . equals ( "" )) continue ;
if ( "+-" . indexOf (str) != - 1 ){
int num2 = stack . pop ();
int num1 = stack . pop ();
if ( str . equals ( "+" )) stack . push (num1 + num2);
if ( str . equals ( "-" )) stack . push (num1 - num2);
} else {
stack . push ( Integer . parseInt (str));
}
}
return stack . pop ();
}
} Shunting Yard Algorithm 的做法同上，加一个优先级就行。
Copy public class Solution {
public int calculate ( String s) {
return evalRPN(getRPN(s)) ;
}
private String getRPN ( String s){
StringBuilder sb = new StringBuilder() ;
Stack < Character > stack = new Stack <>();
for ( int i = 0 ; i < s . length (); i ++ ){
char chr = s . charAt (i);
if (chr == ' ' ) continue ;
if ( Character . isDigit (chr)){
sb . append (chr);
} else {
sb . append ( ' ' );
if (chr == '(' ){
stack . push (chr);
} else if (chr == ')' ){
while ( stack . peek () != '(' ){
sb . append ( stack . pop ());
sb . append ( ' ' );
}
stack . pop ();
} else {
while ( ! stack . isEmpty () && getPrecedence(chr) <= getPrecedence( stack . peek()) ){
sb . append ( stack . pop ());
sb . append ( ' ' );
}
stack . push (chr);
}
}
}
while ( ! stack . isEmpty ()){
sb . append ( ' ' );
sb . append ( stack . pop ());
}
return sb . toString ();
}
private int evalRPN ( String s){
String [] strs = s . split ( " " );
Stack < Integer > stack = new Stack <>();
for ( String str : strs){
if ( str . equals ( "" )) continue ;
// Is operator
if ( "+-*/" . indexOf (str) != - 1 ){
int num2 = stack . pop ();
int num1 = stack . pop ();
if ( str . equals ( "+" )) stack . push (num1 + num2);
if ( str . equals ( "-" )) stack . push (num1 - num2);
if ( str . equals ( "*" )) stack . push (num1 * num2);
if ( str . equals ( "/" )) stack . push (num1 / num2);
} else {
stack . push ( Integer . parseInt (str));
}
}
return stack . pop ();
}
private int getPrecedence ( char chr){
if (chr == '*' || chr == '/' ) return 3 ;
if (chr == '+' || chr == '-' ) return 2 ;
return 0 ;
}
} 
