1/20, String 构造式 DFS+Backtracking

• 比较特殊的做法是，从String中每个字符的角度出发，去考虑“拿/不拿”。这个方法，简单直接又好分析时间复杂度。

• StringBuilder 的构造式 DFS + Backtracking，对 “加 / 不加” 的先后顺序是敏感的，下面两题中，同样的代码，都是 先走“不加”的分支 再走“加”的分支 原因在于，这个模板是 “带着当前考虑元素” 的 DFS，在当前函 数尾部回溯。当两个 dfs 同处一层，而同层 dfs 只在最尾部才回 溯的时候，如果先跑添加的分支，会在后面执行不添加分支时候 出错。

Generalized Abbreviation

这题完全可以从 word 出发，以 length 和 pos 的角度遍历去 DFS 解决，比较符合 大多数搜索问题的状态空间结构。 然而 “字符串构造式 DFS + backtracking”，还有最简单直接又 好分析时间复杂度的做法，就是从 String 中每个字符的角度出 发，去考虑 “拿 / 不拿”

length 和 pos 角度：

time complexity: O(2 ^ n) n is the length of the word

space complexity: O(n)

class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> res = new ArrayList<>();
        helper(res, word, 0, "", 0);
        return res;
    }

    private void helper(List<String> res, String word, int pos, String cur, int count) {
        if (pos == word.length()) {
            if (count > 0) cur += count;
            res.add(cur);
            return;
        } 

        helper(res, word, pos + 1, cur, count + 1);   // abbreviate letter
        helper(res, word, pos + 1, cur + ((count > 0) ? count : "") + word.charAt(pos), 0);   // keep letter
    }
}

每个字符去留角度：用一个StringBuilder 来存储所有的可能的字符

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());
            sb.setLength(len);
            return;
        } 

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

valid parenthese

use stack when there are multiple pairs of parentheses:

class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;

        int n = s.length();
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) != -1) {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                if ((c == ')' && stack.peek() != '(') ||
                    (c == ']' && stack.peek() != '[') ||
                    (c == '}' && stack.peek() != '{')) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

alternatively, when considering one kind of parentheses, we can use a count variable to check whether it is valid:

• count('(') < count(')'), i < n - 1
• count('(') == count(')'), i = n - 1
• time complexity: O(n)

    private static boolean process(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (count < 0) return false;
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
            }
        }
        return count == 0;
    }

Remove Invalid Parentheses

分解这道题为三个步骤：

• 计算最小数量的左右要删除的括号, leftCount: 要删除的左括号数量，rightCount: 要删除的右括号数量，openCount: 被认为valid的左右括号数量
• dfs去尝试各种可能的解
  • 注意出口条件，提早剪枝

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

        int leftCount = 0;
        int rightCount = 0;
        int openCount = 0;

        // get all the number of left and right parenthese that we need to remove
        for (char c : s.toCharArray()) {
            if (c == '(') leftCount++;
            if (c == ')') {
                if (leftCount > 0) leftCount--;
                else rightCount++;
            }
        }
        // dfs to search
        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;

        int len = sb.length();
        char c = str.charAt(index);

        if (c == '(') {
            //remove
            dfs(set, str, index + 1, leftCount - 1, rightCount, openCount, sb);
            //keep
            dfs(set, str, index + 1, leftCount, rightCount, openCount + 1, sb.append(c));

        } else if (c == ')') {
            //remove
            dfs(set, str, index + 1, leftCount, rightCount - 1, openCount, sb);
            //keep
            dfs(set, str, index + 1, leftCount, rightCount, openCount - 1, sb.append(c));
        } else {
            // other character,
            dfs(set, str, index + 1, leftCount, rightCount, openCount, sb.append(c));
        }

        sb.setLength(len);
    }
}