String 类动态规划

log 11-23 9:14pm Bobst 11-25 3:15pm Home 11-26 10:58pm Home WordBreakII

  • Longest Common Sequence
  • One Edit Distance (Snapchat)
  • Edit Distance
  • Palindrome Edit Distance
  • Wildcard Matching
  • Regular Expression Matching
  • Word Break
  • Word Break II

这个系列都是Snapchat爱考的类型

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

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

用dp[i][j]表示第一个string 的前i项和第二个string的前j项的匹配情况。

Longest Common Sequence

从最简单的问题开始

当前两个字符匹配的时候，同时移动坐标 如果不匹配的时候，只移动一个的坐标

可视化版本

if(A.charAt(i - 1) == B.charAt(j - 1)) {
    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
} else {
    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);    
}

One Edit Distance (Snapchat)

很容就照搬LCS的做法，去看有多少个mismatch的字符，然后判断是否等于一。O(mn)的解法。

但是这题因为只有一个edit distance，所以不需要保存那么多状态，可以有更直接的做法。

在mismatch的位置就可以判断：

让 n, m 为两个 String 的长度 如果 m == n ，mismatch 之后的子字符串一定完全相等； 否则长的那段在 i 之后的 substring 一定与短的以 i 开始的 substring 全等； 如果在循环末尾还没有发现 mismatch，两个字符串末尾必然会有 1 的长度差，否则 S == T.

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

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

        for(int i = 0; i < Math.min(m, n); i++) {
            if(s.charAt(i) != t.charAt(i)) {
                if(m == n) {
                    // replace
                    return s.substring(i + 1).equals(t.substring(i + 1));
                } else {
                    // add or delete
                    return s.substring(i + 1).equals(t.substring(i)) || s.substring(i).equals(t.substring(i + 1));
                }
            }
        }       
        return Math.abs(m - n) == 1;
    }
}

Edit Distance

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

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

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

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // 1的前i项和2的前j项 相同最小需要多少步
        int[][] dp = new int[m + 1][n + 1];

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

        for(int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for(int i = 1; i <= m; i++ ){
            for(int j = 1; j <= n; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1) ) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // substitue
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    // add: dp[i][j - 1], i 比 j - 1 多一项，说明i加了一项
                    // del: dp[i- 1][j] , i - 1比 j 少一项，说明i减了一项
                    dp[i][j] = Math.min(dp[i][j], Math.min(dp[i][j - 1], dp[i - 1][j]) + 1 ) ;
                }
            }
        }
        return dp[m][n];
    }
}

Palindrome Edit Distance

Snapchat

给一个string，算出把他变成palindrome的最少操作数。操作包括，增加，删减以及修改。

和Edit Distance很像，是一道区间型的动态规划，

问题的 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/replace 操作构造出当前的 s(i, j)

s(i + 1, j) + 1 : ADD

s(i, j - 1) + 1 : delete

s(i - 1, j + 1) + 1 : replace

public int miniEditDistance(String s) {
    if (s == null || s.length() <= 1 ) {
        return 0;
    }

    int len = s.length();

    // substring[i, j] 是palindrome的最小操作数是多少
    int[][] dp = new int[len][len];

    // init skip, dp[i][i] = 0,  dp[i][i + 1] = 0

    for(int i = 1; i < len; i++) {
        for(int j = i; j >= 0; j--) {
            if(i == j) {
                dp[i][i] = 0;
            } else if(i == j + 1 && s.charAt(i) == s.charAt(j)) {
                dp[j][i] = 0;
            } else if(i == j + 1 && s.charAt(i) != s.charAt(j)) {
                dp[j][i] = 1;
            } else if(s.charAt(i) == s.charAt(j)) {
                dp[j][i] = dp[j + 1][i - 1];
            } else if(s.charAt(i) != s.charAt(j)) {
                dp[j][i] = Math.min(dp[j + 1][i - 1], 
                    Math.min(dp[j + 1][i], dp[j][i - 1])) + 1;
            }
        }
    }

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

// version 2 区间型动归标准写法
public int miniEditDistance(String s) {
    if (s == null || s.length() <= 1 ) {
        return 0;
    }

    int len = s.length();

    // substring[i, j] 是palindrome的最小操作数是多少
    int[][] dp = new int[len][len];

    // init skip, dp[i][i] = 0
    for(int i = 0; i < len - 1; i++) {
        if(s.charAt(i) != s.charAt(i + 1)) {
            dp[i][i + 1] = 1;
        }
    }

    // s(i + 1, j) + 1 : 在左边ADD或者delete
    // s(i, j - 1) + 1 : 在右边ADD或者delete
    // s(i - 1, j + 1) + 1 : replace
    for(int l = 2; l < len; l++) {
        for(int i = 0; i + l < len; i++) {
            if(s.charAt(i) == s.charAt(i + l)) {
                dp[i][i + l] = dp[i + 1][i + l - 1];
            } else {
                dp[i][i + l] = Math.min(dp[i + 1][i + l - 1], 
                    Math.min(dp[i + 1][i + l], dp[i][i + l - 1])) + 1;
            }
        }
    }

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

Wildcard Matching

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

首先我们可以观察到最终结果只需要返回 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][j - 1] (忽略 p[j] 的存在)
    • match 多个字符，看 dp[i - 1][j]（包含匹配一个） 注意这里由于循环结构的关系，其实对于每一个 j ，我们会去考虑 [0, i-1] 所有的可能性，所以可以用一个状态指代所有前面的 match.
    • 只 match 当前一个字符，看 dp[i - 1][j - 1]; LeetCode 测试了下，其实这行拿掉也是正确的

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

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

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

        dp[0][0] = true;
        // 易错点
        // 从头开始连续 '*' 匹配空串的时候
        for(int i = 1; i <= n; i++) {
            if(p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else break;
        }

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; 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[0][j]传递而来
                    dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }
}

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

双指针的做法

public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0, star = -1, match = 0;

        while(i < s.length()) {
            if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') ) {
                i++;
                j++;
            } else if(j < p.length() && p.charAt(j) == '*' ){
                star = j++;
                match = i;
            // 有*，？ 匹配不上就用之前的*来匹配
            } else if(star != -1) {
                // backtracking
                j = star + 1;
                match++;
                i = match;
            } else {
                return false;
            }

        }
        while(j < p.length() && p.charAt(j) == '*') {
            j++;
        }
        return j == p.length();
    }
}

Regular Expression Matching

'.' Matches any single character. '*' Matches zero or more of the preceding element.

  • 和之前的一个字符组合起来匹配 这里我们需要假设 p 不会以星号开始，也不会有连续多个星号出现，不然现有题意描述是无法解决这些问题的。

对于pattern来说

  • 遇到p[j] 是'*'的时候
    • 如果p[j - 1]是'.' 或者p[j - 1] == s[i] 那么这个星号
      • dp[i - 1][j] 匹配一个或者多个字符
      • dp[i][j - 1] 只让p[i - 1]匹配，星号不匹配
      • dp[i][j - 2] 都不匹配
    • 不是'.' 都不匹配

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

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

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

        dp[0][0] = true;
        // the first char cannot be asterisk
        // 匹配空串
        for(int i = 2; i <= n; i++) {
            if(p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }

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

                if(cs == cp || cp == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if(cp == '*') {
                    char prev = p.charAt(j - 2);
                    if(prev == cs || prev == '.') {
                        // 匹配多个，不匹配和不匹配星号的情况
                        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[m][n];
    }
}

Word Break

因为是找substring，所以第一个想法是建一个dp[i][j],得以覆盖掉所有的可能。

但是其实我们只用记录 最后一刀切在哪儿就可以了。 如果最后一刀切的位置到当前位置的substring在 dict里面，就update最后一刀的位置。

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

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

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

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

public class Solution {
    public boolean canBreak(String s, Set<String> dict) {
        int len = s.length();

        boolean[] can = new int[len + 1];
        can[0] = true;

        for(int i = 1; i <= len; i++) {
            for(int j = i; j >= 0; j--) {
                if(!can[j]) continue;
                if(dict.contains(s.substring(j, i))) {
                    can[i] = true;
                }
            }
        }

        return can[len];
    }
}

Word Break II

这题可以直接dfs + backtracking 硬搜，但是这样时间复杂度很高， O(2^n)

如何优化时间复杂度呢？

  • 预处理：建立boolean[][] 表示可能的区间内是不是word，方便dfs判断要不要进入下一层的循环
public class Solution {
    public List<String> wordBreakII(String s, Set<String> dict) {
        int len = s.length();

        boolean[] can = new boolean[len + 1];
        boolean[][] dp = new boolean[len + 1][len + 1];

        can[0] = true;

        for(int i = 1; i <= len; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if(can[j] && dict.contians(s.substring(j, i))) {
                    can[i] = true;
                    dp[j][i] = true;
                }
            }
        }

        List<String> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, result, path, len, dp);

        return result;
    }

    private void dfs(String s, List<String> result, List<String> path, int pos, boolean[][] dp) {
        if(pos == 0) {
            StringBuilder sb = new StringBuilder();
            for(int i = path.size() - 1; i >= 0; i--) {
                sb.append(path.get(i) + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            result.add(sb.toString());
            return;
        }

        for(int i = 0; i < s.length(); i++) {
            if(dp[i][pos]) {
                path.add(s.substring(i, pos));
                dfs(s, result, path, i, dp);
                path.remove(path.size() - 1);
            }
        }
    }
}

results matching ""

    No results matching ""