String 构造式 DFS

完成：11/8

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

StringBuilder 的构造式 DFS + Backtracking，对 “加 / 不加” 的先后顺序是敏感的， 都是 先走“不加”的分支 再走“加”的分支

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

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

Generalized Abbreviation

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

    private void dfs(char[] word, List<String> result, StringBuilder sb, int index, int num) {
        int len = sb.length();
        if(index == word.length) {
            if(num != 0) sb.append(num);
            result.add(sb.toString());
        } else {
            // 不拿
            dfs(word, result, sb, index + 1, num + 1);
            // 拿
            if(num != 0) sb.append(num + "");
            dfs(word, result, sb.append(word[index]), index + 1, 0);
        }
        // backtracking
        sb.setLength(len);
    } 
}

Remove Invalid Parentheses

考点： 用什么方法做： 先扫一遍原 string ，记录下需要移除的左括号数量和右括号数量，保证最后的解最优；

描述算法过程： 于是开始 DFS，对于每一个新的字符，我们都有两个选择：'留' 或者 '不留'，就像二叉树的分叉一样，留下了 dfs + backtracking 的空间。

于是当我们针对各种情况进行 dfs 的时候，我们一定可以考虑到所有可能的有效 path，接下来需要定义什么是 “有效 path”， 就是open == 0.

怎么样保证左右括号的匹配，用什么数据结构： 两个variable保存

如何保证最优解: prune操作, 如果在任何时刻，左右括号和开括号的数量为负，我们都可以直接剪枝返回。

O(2^n)

可能的问题： open 变量有什么用？

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> set = new HashSet<>();

        int rmL = 0;
        int rmR = 0;

        // count how many parenthese need to be removed
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') rmL++;

            if(s.charAt(i) == ')') {
                if(rmL != 0) rmL--;
                else rmR++;
            }
        }
        dfs(s, set, 0, rmL, rmR, 0, new StringBuilder());

        return new ArrayList<String>(set);
    }

    public void dfs(String s, Set<String> set, int i, int rmL, int rmR, int open, StringBuilder sb) {
        // base case 是左右括号和开括号数量都为零，并且 index 读取完了所有字符，则把结果添加进去；
        if(i == s.length() && rmL == 0 && rmR == 0 && open == 0) {
            set.add(sb.toString());
            return;
        }

        // exit condition
        if(i >= s.length() || rmL < 0 || rmR < 0 || open < 0) {
            return;
        }

        char c = s.charAt(i++);
        // mark
        int len = sb.length();

        if(c == '(') {
            // drop it
            dfs(s,set,i,rmL - 1,rmR, open, sb);
            // add it
            dfs(s,set,i,rmL,rmR,open + 1, sb.append(c));
        } else if(c == ')') {
            // drop 
            dfs(s,set,i,rmL,rmR - 1,open,sb);
            // add
            dfs(s,set,i,rmL,rmR,open - 1,sb.append(c));
        } else {
            // add it 
            dfs(s,set,i,rmL,rmR,open,sb.append(c));
        }
        // backtracking
        sb.setLength(len);
    }
}

Expression Add Operators

难题，很少会考察到，重点是思维的训练，不要求bug-free的写出来。

在每一个可能加入运算符的位置上，逐个尝试乘法，加法和减法。

注意点： 为了避免取到000这样的数，如果 start 位置是 0 而且当前循环的 index 还是 0，直接 return

流程：

• dfs + backtracking 思路
• dfs 函数中存 "左面表达式的当前值" 和 "上一步操作的结果" (用于处理优先级)
• 参数都用 Long，防止溢出，毕竟 String 可能是个大数
• start == 0 的时候，直接考虑所有可能的起始数字扔进去，同时更新 cumuVal 和 prevVal;
• 除此之外，依次遍历所有可能的 curVal parse，按三种不同的可能操作做 dfs + backtracking;
  • 加法：直接算，prevVal 参数传 curVal，代表上一步是加法；
  • 减法：直接算，prevVal 参数传 -curVal，代表上一步是减法；
  • 乘法：要先减去 prevVal 抹去上一步的计算，然后加上 prevVal， curVal 代表当前值；同时传的 preVal 参数也等于 prevVal curVal.
  • 乘法操作这种处理方式，在遇到连续乘法的时候可以看到是叠加的；但是前一步操作如果不是乘法，则可以优先计算乘法操作。

public class Solution {

    List<String> res = new ArrayList();

    public List<String> addOperators(String num, int target) {
        helper(num, target, "", 0, 0);
        return res;
    }

    private void helper(String num, int target, String tmp, long currRes, long prevNum){
        // 如果计算结果等于目标值，且所有数都用完了，则是有效结果
        if(currRes == target && num.length() == 0){
            res.add(exp);
            return;
        }
        // 搜索所有可能的拆分情况
        for(int i = 1; i <= num.length(); i++){
            String currStr = num.substring(0, i);
            // 对于前导为0的数予以排除
            if(currStr.length() > 1 && currStr.charAt(0) == '0'){
                // 这里是return不是continue
                return;
            }
            // 得到当前截出的数
            long currNum = Long.parseLong(currStr);
            // 去掉当前的数，得到下一轮搜索用的字符串
            String next = num.substring(i);
            // 如果不是第一个字母时，可以加运算符，否则只加数字
            if(tmp.length() != 0){
                // 乘法
                helper(next, target, tmp+"*"+currNum, (currRes - prevNum) + prevNum * currNum, prevNum * currNum);
                // 加法
                helper(next, target, tmp+"+"+currNum, currRes + currNum, currNum);
                // 减法
                helper(next, target, tmp+"-"+currNum, currRes - currNum, -currNum); 
            } else {
                // 第一个数
                helper(next, target, currStr, currNum, currNum);
            }
        }
    }
}