7/2, 字符串类

字符串 DP 类的很多典型问题，用这一张图都能说明白：

两个 String 放一起，从某个位置开始看看是否 match; 要是不 match 了，就得错开一位看；要是 match 了，就都往后挪一位看。在 Edit Distance 里面，稍微特殊一点，因为我们还有一个 replace 操作，可以直接修正当前 mismatch，让两个字符串都挪动一格位置。

于是对于每一个 String，就有了一个对于其位置敏感的维度 dp[i]，代表从最左面开始的 i 个字符构成的字符串，也是子问题的结构定义。因为我们有两个 String 并且需要枚举位置之间可能的各种交错穿插，我们就需要两个维度 dp[i][j]，代表第一个字符串中的 i 个字符和第二个字符串中的 j 个字符匹配情况。

Longest Common Subsequence (CLRS)

研究一个新问题时，最好还是从算法导论开始。

给定长度为 m 的字符串 {1,2,3...m} ，其 subsequences 的数量总数为 2^m，即对每个字符选择 “取 / 不取”。

于是有了下面的可视化版本~

这个版本的做法非常适合存储和输出 optimal path，也可以应用到 Longest Increasing Subsequence 中，用于 follow-up 情况下输出 sequence.

比如输入数组为 X = [x1, x2 .. xn]，其排序后的数组为 X' = [x'1, x'2 .. x'n]

• LIS 即 X 与 X' 的 LCS，判断条件完全一样，元素相等向右下走。如果每一步上都存行进方向，那么最后从右下角往左上出发，每一步指向左上角的箭头都是 LIS 的元素。

滚动数组优化版的代码.

最大值肯定在 dp[][] 的最右下角。

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if(A == null || B == null) return 0;
        int n = A.length();
        int m = B.length();
        if(n == 0 || m == 0) return 0;

        int[][] dp = new int[2][m + 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(A.charAt(i - 1) == B.charAt(j - 1)){
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1; 
                } else {
                    dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]); 
                }

            }
        }

        return dp[n % 2][m];
    }
}

One Edit Distance

一开始未经思考尝试以 LCS 长度判断，但是这个思路是错的，因为 S 和 T 的 LCS 长度可以满足条件，但是 mismatch 的字符却不一定是在同一个位置。况且， LCS 的时间复杂度是 O(mn), 这题应该很明显有 O(n) 的解法。

正解借鉴了论坛的代码，其实非常简洁。

核心思想是，既然有且只有 1 个位置 mismatch，我们可以直接在找到 mismatch 位置上判断：

• 让 n, m 为两个 String 的长度

• 如果 m == n ，mismatch 之后的子字符串一定完全相等；

• 否则长的那段在 i 之后的 substring 一定与短的以 i 开始的 substring 全等；

• 如果在循环末尾还没有发现 mismatch，两个字符串末尾必然会有 1 的长度差，否则 S == T.

在字符串 DP 中，原始字符串上的 substring，等价于原始区间内的 subproblem.

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int n = s.length();
        int m = t.length();

        if(Math.abs(n - m) > 1) return false;

        for(int i = 0; i < Math.min(m,n); i++){
            if(s.charAt(i) != t.charAt(i)){
                if(n == m) return s.substring(i + 1).equals(t.substring(i + 1));
                if(n > m) return s.substring(i + 1).equals(t.substring(i));
                if(n < m) return s.substring(i).equals(t.substring(i + 1));
            }
        }

        return Math.abs(n - m) == 1;
    }
}

Edit Distance

结合上一道题的错误来看，可以很容易看到只依靠 LCS 长度解决这道题的乏力；因为 LCS 长度和 edit distance 对字符串结构的利用是不一样的，mismatch 的字符可以出现错位，而 edit distance 不支持一次操作进行修正。算法导论上也写的非常清楚，鉴定两条 DNA 序列的相似度，substring 是一种思路（KMP），LCS是一种思路，而 edit distance 是另一种思路。

关于这个问题最好的 slides, by Stanford

然而相同的是，这道题思考并寻找 optimal substructure 的思路是非常接近的，都是直接从最终答案 String Z 的结构 top-down 往回看。因为对于每个 string，我们对其任意操作都会构造出来一个只与它自己相差一个字符的新 string.

• S[1,2,3..n] 为 String S;

• T[1,2,3..m] 为 String T;

• Z[1,2...k] 为最少修改之后的 String Z;

  • 注意这里 Z 可以有多个正解，因为可以有多个最优的正确操作。

  • 类似于 LCS，Z 也可以是多条路径。

于是；

• 若 S[n] == T[m] ，则Z[1,2.. k - 1] 为 S[n - 1] 和 T[m - 1] 的解；

• 若 S[n] != T[m]:

  • 最优解为 S[1,2 ..n] 与 T[1,2 .. m - 1] 构造而成，

    • 删掉 S[n]

    • OR 增加 T[m];

  • 最优解为 S[1,2 .. n - 1] 与 T[1,2 .. m] 构造而成

    • 删掉 T[m]

    • OR 增加 T[n];

  • 最优解为 S[1,2 .. n - 1] 和 T[1,2 .. m - 1] 构造而成

    • 直接把 S[n] 和 T[m] replace 成一样的。

来自 Stanford 课件，bottom - up 的 String 构造法。我们定义 D(i, j - 1) 为 insertion 是因为 i 是外循环位置，j 是内循环位置；因此当 i 固定，相对于 j 取了前一个位置 + 新字符的时候是 j 的 insertion； 而 D(i - 1, j) 代表 j 在新循环中并没有增加长度，反而从 i 里删除了。

考虑到所有操作都在双循环内完成，调换循环位置并不会影响算法正确性，但是会赋予每次操作相反的意义，即调换等价互补操作 "S + 1" 和 "T - 1".

其实和算法导论的图是一个意思，方向不同而已。

如果这题每种操作附带了 cost ，要求最小的 cost 怎么办？

不难看出，add 和 delete 作为互补操作，其 cost 是一样的；即使不一样，我们也可以在两个 String 的构造过程中，总是选择更小的那个。

public class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n + 1][m + 1];

        for(int i = 1; i <= n; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= m; i++){
            dp[0][i] = i;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                // 注意这步考虑 dp[i - 1][j - 1]同时再考虑 
                // min(dp[i - 1][j], dp[i][j - 1]) + 1 也合乎逻辑，一样可以 AC 
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], 
                               Math.min(dp[i - 1][j], 
                                        dp[i][j - 1])) + 1; 
                }
            }
        }
        return dp[n][m];
    }
}

(Google, Snapchat面经)

Minimum insertions to form a palindrome

和 Edit distance 非常像，考虑到 add/delete 在构造 string 上的等价性质，问题的 optimal substructure 即为

• dp[i][j] = substring(i,j) 范围内，构造 palindrome 的最小编辑次数

  • 如果 s[i] == s[j]

    • dp[i][j] = dp[i + 1][j - 1] (不需要操作)

    • 同时考虑 i , j 相邻的情况

  • 如果 s[i] != s[j]，那么我们可以经 add/delete 操作构造出当前的 s(i, j)

    • s(i + 1, j) + ADD

    • s(i, j - 1) + ADD

注意这题不支持 replace，如果支持的话，dp[i][j] 还要看一个新状态，dp[i + 1][j - 1]

public class Main {
    private static int minEditDistance(String str){
        if(str == null || str.length() <= 1) return 0;

        int n = str.length();

        // dp[i, j] = min edit distance for substring (i , j);
        int[][] dp = new int[n][n];
        for(int i = 1; i < n; i++){
            for(int j = i; j >= 0; j--){
                if(j == i) {
                    dp[j][i] = dp[i][j] = 0;
                } else {
                    if(str.charAt(i) == str.charAt(j)){
                        dp[j][i] = dp[i][j] = (j + 1 == i) ? 0
                                : dp[j + 1][i - 1];
                    } else {
                        dp[j][i] = dp[i][j] = (j + 1 == i) ? 1
                                : Math.min(dp[j + 1][i], dp[j][i - 1]) + 1;
                    }
                }
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args){
        System.out.println(minEditDistance("geekforgeeks"));
    }
}

WildCard Matching

Hard 难度题，字符串 DP.

首先我们可以观察到最终结果只需要返回 true / false ，而不是很在乎具体到哪个位置的时候 wildcard 匹配了什么字符，所以是一个用 DP 的信号。

顺着这个思路想，这题具有这章其他 DP 类问题都非常相似的结构和 optimal substructure ，即都是 1 / 2 个 string 从小往大“生长”，每一步需要做 match 的判断构造出更长 string 的正解；以这题的结构，不难想出 dp 的数组结构就是 dp[i][j] 代表 s 的前 i 个字符串能否和 p 的前 j 个字符串成功匹配，以 dp[n][m] 为最终解。

剩下的问题就是，如何正确识别所有情况。

s[i] , p[j] 为 s , p 的第 i / j 个字符，略去 off-by-one 的 index 问题

• 当 p[j] = 常规字母时；

  • 如果 s[i] == p[j]，当前位置 match;

  • 同时如果之前的字符串 dp[i - 1][j - 1] 也 match ，则 dp[i][j] match;

• 当 p[j] 为 '?' 时；

  • 当前位置一定 match，只看 dp[i - 1][j - 1] 是否也 match;

• 当 p[j] 为 '*' 时；

  • 只 match 当前一个字符，看 dp[i - 1][j - 1];

    • LeetCode 测试了下，其实这行拿掉也是正确的

  • 不 match 任何字符，看 dp[i][j - 1] (忽略 p[j] 的存在)

  • match 多个字符，看 dp[i - 1][j]

    • 注意这里由于循环结构的关系，其实对于每一个 j ，我们会去考虑 [0 , i-1] 所有的可能性，所以可以用一个状态指代所有前面的 match.

最后要注意一下 dp[0][0], dp[0][i] 的初始化。

    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        int n = s.length();
        int m = p.length();

        boolean[][] dp = new boolean[n + 1][m + 1];

        dp[0][0] = true;

        for(int i = 1; i <= m; i++){
            if(p.charAt(i - 1) == '*') dp[0][i] = true;
            else break;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(p.charAt(j - 1) == '?' || 
                   s.charAt(i - 1) == p.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                } else if(p.charAt(j - 1) == '*'){
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }

        return dp[n][m];
    }

Regular Expression Mathcing

也是 Hard 题，长得还和 Wildcard Matching 特别像。

最大的不同是，在这里 '*' 号是和其前一个字符有联系的，和其前一个字符一起，代表着“多个或0个星号前面的字符”。 这里我们需要假设 p 不会以星号开始，也不会有连续多个星号出现，不然现有题意描述是无法解决这些问题的。

• 遇到常规字母和 '.' 的处理和上一题没有任何区别；

• 遇到 p[j] 为星号时：

  • 如果 p[j - 1] 是 '.', 那么这个星号

    • dp[i - 1][j] 以当前星号匹配一个或多个多个字符；

    • dp[i][j - 1] 只让 p[j - 1] 匹配，当前星号不匹配字符；

    • dp[i][j - 2] 同下。

  • 否则，星号位置能否匹配取决于 dp[i][j - 2]，即让(p[j - 1] + 当前星号)都不匹配任何字符。

以这两道题看，dp[i - 1][j] 都代表着 “以 p 当前 * 字符，匹配 s 的[1,n]长度字符”

这题dp[0][i]初始化和 Wildcard 不太一样，因为会有 c*a*b 这种情况，多个星号跳着出现，不要立刻 break 掉，而要扫到底，dp[0][i] 要看 dp[0][i - 2];

    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        int n = s.length();
        int m = p.length();

        boolean[][] dp = new boolean[n + 1][m + 1];

        dp[0][0] = true;

        for(int i = 2; i <= m; i++){
            if(p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 2];
        }


        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                char chars = s.charAt(i - 1);
                char charp = p.charAt(j - 1);

                if(charp == '.' || charp == chars){
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (charp == '*'){
                    char charPrev = p.charAt(j - 2);
                    if(charPrev == '.' || charPrev == chars){
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2] || dp[i][j - 1];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }

        return dp[n][m];
    }

Word Break

这是一道很像 rod-cutting 还有 palindrome paritioning 的题，利用的结构也一样。

要保证算法的正确性，我们要迭代考虑题目中所有的 substring 组合，不然可能会漏掉正解。考虑到题目可能的 substring 数量，这题的时间复杂度至少为 O(n^2)，因此我们能做的就是利用好 substring 相互覆盖的地方避免重复计算。

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[][] canBreak = new boolean[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i; j >= 0; j--){
                String str = s.substring(j, i + 1);
                if(wordDict.contains(str)) canBreak[i][j] = canBreak[j][i] = true;
                if(j > 0 && canBreak[j][i] && canBreak[0][j - 1]) canBreak[0][i] = canBreak[i][0] = true;
            }
        }

        return canBreak[0][n - 1];
    }
}

在如上代码 AC 之后，思考之后可以发现两个很明显的优化：

optimal substructure 是，如果 [0, j] 可以 break 并且 [j + i , i] 在字典里，那么 [0 , j] 就可以 break.

• 我们不需要存储所有区间是否可以 break，只取从 index = 0 开始到 i 为止是否可以就行了；空间优化成了 O(n);

• 因此如果回头扫到了当前位置可以 break 的时候，我们就可以做 early termination.

• 同时对于每个考虑的中间位置 j ，如果在 j 上不能 break，那么取 substring 和检查字典的必要都没有。

    public boolean wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[] canBreak = new boolean[n + 1];
        canBreak[0] = true;

        for(int j = 1; j <= n; j++){
            for(int i = j; i >= 0; i--){
                if(!canBreak[i]) continue;
                String str = s.substring(i, j);
                if(wordDict.contains(str)) canBreak[j] = true;
            }
        }

        return canBreak[n];
    }

Word Break II

这题有简单暴力的 dfs + backtracking，然而为了优化计算时间，也要利用备忘录法和记忆化搜索。

这题做出来容易，AC 有点难，因为用时卡的厉害，有坑爹的 test case :

【s ="aaaaaaaaaaaaaaaaa...aaaa" , dict = "a", "aa", "aaa", "aaaa"】

硬搜的时间复杂度为 O(2^n)，搜索树结构见算法导论的 rod-cutting.

最容易想到的几种优化方式：

• 预处理，建 boolean[][] 表示所有可能区间内是不是 word，方便dfs 时判断要不要进入下一层循环；

• 记录字典里最长单词长度作为 step size，dfs 每次循环寻找位置时限制最远的搜素距离；（用于优化 s 相对于 word 非常长的情况）

然而单独靠以上两种优化都还不够。。

https://leetcode.com/discuss/80266/java-dfs-memoization-dfs-and-pruning-solutions-with-analysis

事实证明在这题里，直接用 HashSet + substring 检查字典，要比预处理计算 boolean[][] 快。 (8ms vs. 22ms)

O(len(wordDict) ^ len(s / minWordLenInDict))

Because there're len(wordDict) possibilities for each cut，同时空间占用可能会比较大。

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[][] isWord = new boolean[n][n];
        int maxLength = 0;

        for(String str : wordDict){
            maxLength = Math.max(maxLength, str.length());
        }

        return dfs(s, wordDict, new HashMap<Integer, List<String>>() , 0, maxLength);
    }

    private List<String> dfs(String s, Set<String> wordDict, HashMap<Integer, List<String>> map, int start, int maxLength){
        if(map.containsKey(start)) return map.get(start);

        List<String> rst = new ArrayList<String>();
        if(start >= s.length()) rst.add("");
        for(int i = start; i - start <= maxLength && i < s.length(); i++){
            String str = s.substring(start, i + 1);

            if(wordDict.contains(str)){
                List<String> afterWards = dfs(s, wordDict, map, i + 1, maxLength);
                for(String next : afterWards){
                    if(i + 1 < s.length()) rst.add(str + " " + next);
                    else rst.add(str);
                }
            }
        }

        map.put(start, rst);
        return rst;
    }
}

Interleaving String

首先从题目结构来看，和这章的前几道字符串 DP 非常相似，都是一个字符串 “构造问题”，即用小的 substring 通过生长和拼接，构造出更大的目标 string. 一般这类问题有天然的 bottom-up 思路，当然，top-bottom 的递归思路也是完全可行的。

首先贴一个自己写的暴力解法，三维 dp，dp[i][j][k] 代表着“s1 的前 i 个字符和 s2 的前 j 个字符，能否构造成 s3 的前 k 个字符”。

下面代码时间复杂度 O(s1.len * s2.len * s3.len)，可以 AC，但是显然还有优化的空间。

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1 == null || s2 == null || s3 == null) return false;
        if(s3.length() != s1.length() + s2.length()) return false;
        if(s1.length() == 0) return s2.equals(s3);
        if(s2.length() == 0) return s1.equals(s3);

        int s1Len = s1.length();
        int s2Len = s2.length();
        int s3Len = s3.length();
        // dp[i][j][k] if the first i chars from s1 and first j chars from s2
        // can interleave to produce first k chars of s3

        boolean[][][] dp = new boolean[s1Len + 1][s2Len + 1][s3Len + 1];

        dp[0][0][0] = true;

        for(int k = 1; k <= s3Len; k++){
            char char3 = s3.charAt(k - 1);

            for(int i = 1; i <= k && i <= s1Len; i++){
                char char1 = s1.charAt(i - 1);
                for(int j = 1; j <= k && j <= s2Len; j++){
                    char char2 = s2.charAt(j - 1);

                    if(char1 == char3 && k - i >= 0 && k - i <= s2Len && dp[i - 1][k - i][k - 1]) {
                        dp[i][k - i][k] = true;
                    }
                    if(char2 == char3 && k - j >= 0 && k - j <= s1Len && dp[k - j][j - 1][k - 1]) {
                        dp[k - j][j][k] = true;
                    }

                }
            }
        }

        return dp[s1Len][s2Len][s3Len];
    }
}

简单观察之后发现正确答案的限制条件： k = i + j，换句话说，k 可以用 i + j 表示出来，因此不需要以 k 作为单独维度遍历。

同时我们也要处理好 i = 0 和 j = 0 的初始化条件。

时间空间复杂度 O(s1.len * s2.len)

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1 == null || s2 == null || s3 == null) return false;
        if(s3.length() != s1.length() + s2.length()) return false;
        if(s1.length() == 0) return s2.equals(s3);
        if(s2.length() == 0) return s1.equals(s3);

        int s1Len = s1.length();
        int s2Len = s2.length();
        // dp[i][j][k] if the first i chars from s1 and first j chars from s2
        // can interleave to produce first i + j chars of s3

        boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];

        dp[0][0] = true;
        for(int i = 0; i < s1Len; i++){
            if(s1.charAt(i) == s3.charAt(i) && dp[i][0]) dp[i + 1][0] = true;
        }
        for(int i = 0; i < s2Len; i++){
            if(s2.charAt(i) == s3.charAt(i) && dp[0][i]) dp[0][i + 1] = true;
        }

        for(int i = 1; i <= s1Len; i++){
            for(int j = 1; j <= s2Len; j++){
                char char1 = s1.charAt(i - 1);
                char char2 = s2.charAt(j - 1);
                char char3 = s3.charAt(i + j - 1);

                if(char1 == char3 && dp[i - 1][j])  dp[i][j] = true;
                if(char2 == char3 && dp[i][j - 1])  dp[i][j] = true;
            }
        }

        return dp[s1Len][s2Len];
    }
}