String 构造式 DFS + Backtracking

然而 “字符串构造式 DFS + backtracking”，还有最简单直接又好分析时间复杂度的做法，就是从 String 中每个字符的角度出发，去考虑 “拿 / 不拿”。

StringBuilder 的构造式 DFS + Backtracking，对 “加 / 不加” 的先后顺序是敏感的，下面两题中，同样的代码，都是

  • 先走“不加”的分支

  • 再走“加”的分支

原因在于，这个模板是 “带着当前考虑元素” 的 DFS，在当前函数尾部回溯。当两个 dfs 同处一层，而同层 dfs 只在最尾部才回溯的时候，如果先跑添加的分支，会在后面执行不添加分支时候出错。

否则就一次 dfs 后面跟着一次 sb.setLength()，也可以。

Generalized Abbreviation

这题完全可以从 word 出发，以 length 和 pos 的角度遍历去 DFS 解决，比较符合大多数搜索问题的状态空间结构。

然而 “字符串构造式 DFS + backtracking”，还有最简单直接又好分析时间复杂度的做法，就是从 String 中每个字符的角度出发，去考虑 “拿 / 不拿”。

超过 93.61%

public class Solution {
    public List<String> generateAbbreviations(String word) {
         List<String> list = new ArrayList<>();
         dfs(list, new StringBuilder(), word.toCharArray(), 0, 0);
         return list;
    }

    private void dfs(List<String> list, StringBuilder sb, char[] word, int index, int curNum){
        int len = sb.length();
        if(index == word.length){
            if(curNum != 0) sb.append(curNum);
            list.add(sb.toString());
        } else {
            // Don't add, merge to current number
            dfs(list, sb, word, index + 1, curNum + 1);

            // Add current char
            if(curNum != 0) sb.append(curNum);
            dfs(list, sb.append(word[index]), word, index + 1, 0);
        }
        sb.setLength(len);
    }
}

Remove Invalid Parentheses

这题的结构就和 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<> 之类的 “子问题结果” 嘛。

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);
    }
}

Expression Add Operators

num = "105", target = 5;

返回 ["10-5", "1x0+5", "1+0x5", "1x05", "1-0x5"] 是错的

  • 不应该直接把 "05" 当成数字；

  • 乘法符号有优先级问题。

在 Different ways to add parentheses 里，这么干没有任何问题，因为默认是加括号的，左右子树可以完全分离，单独求值。

而这题里，用 divide & conquer 无可避免地遇到符号优先级问题。于是看了一圈 LC 论坛，大家的做法其实都是 DFS + backtracking ..

这题非要用 divide & conquer 也不是不行，但是极其麻烦，如图所示：

对于每一个节点，我们需要考虑其左子树的 String, value，还有抹去最后一步运算的 String 与 value .. 对于右子树，我们还需要其抹去第一步运算的 String 与 value 才能正确做 join.

所以说，珍爱生命，有乘法就远离 divide & conquer 吧。

一个思路不错的帖子，这种做法就不用考虑 join了，只要做乘法的时候看它的前一个元素就行；

流程：

  • dfs + backtracking 思路

  • 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 传递过去即可。

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);
            }
        }
    }
}
PreviousStrobogrammatic 数生成NextWord Pattern I & II

Last updated