交错字符串[dfs -＞ 动态规划 -＞ 状态压缩]

前言

对于匹配问题，常见可以进行dfs暴力匹配，空间复杂度虽小，但是时间复杂度指数级。常见的优化方式就是用动规来进行时空复杂度的中和。而动规的状态转移比较单一时（非for去转移），可用滚动数组进行优化。

一、交错字符串

二、指数级->N方 && O(1) ->O(mn) ->O(n)

1、dfs暴力匹配

// 交错字符串。
public class IsInterleave {
    /*
    core：保证一个字符切下来的字串前后的顺序不能变。
    爽指针匹配，一个指针指向s2,一个指针指向s3,遍历s1，让前两个指针去匹配，但是两个指针都相等时，会产生两条路径。
    则可采用dfs + 剪枝来做。
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) return false;

        init(s1, s2, s3);

        return dfs(0, 0, 0);
    }


    String s1, s2, s3;

    private void init(String s1, String s2, String s3) {
        this.s1 = s1;
        this.s2 = s2;
        this.s3 = s3;
    }

    private boolean dfs(int i, int j, int k) {
        // 所以字符按前后顺序匹配完，匹配成功。
        if (k == s3.length()) return true;

        char c1 = i < s1.length() ? s1.charAt(i) : ' ';
        char c2 = j < s2.length() ? s2.charAt(j) : ' ';
        char c3 = s3.charAt(k);

        // 字符匹配.
        return c1 == c3 && dfs(i + 1, j, k + 1) || c2 == c3 && dfs(i, j + 1, k + 1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2、动规规划

/*
    core：保证一个字符切下来的字串前后的顺序不能变。
    爽指针匹配，一个指针指向s2,一个指针指向s3,遍历s1，让前两个指针去匹配，但是两个指针都相等时，会产生两条路径。
    则可采用dfs + 剪枝来做。

    动态规划中和时空复杂度!
    动规核心：找规模更小性质相同的子问题，对于字符串而言，就是切字串！
    状态定义：f[i][j]表示字符串s1[0:i] + s2[0:j]能否交错形成字符串s3[0:i+j+1]
    状态转移：
        // 字符匹配.
        return c1 == c3 && dfs(i + 1, j, k + 1) || c2 == c3 && dfs(i, j + 1, k + 1);
        把这句代码换个表达即可。
        f[i][j] = s1[i] == s3[i+j+1] && f[i-1][j] || s2[j] == s3[i+j+1] && f[i][j-1]
    初始状态：f[0][0] = true;
    最终状态：f[s1.len][s2.len]
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), k = s3.length();

        if (m + n != k) return false;

        // 状态定义，f[i][j]表示s1[i-1]+s2[j-1]=s3[i+j-1]，s1第0-i个字符形成的字串+s2第0-j个字符形成的字串。
        boolean[][] f = new boolean[m + 1][n + 1];
        // 状态初始化，两个空字符成功交错成一个空字符。
        f[0][0] = true;
        // 状态转移
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == j && j == 0) continue;

                char c1 = i != 0 ? s1.charAt(i - 1) : ' ';
                char c2 = j != 0 ? s2.charAt(j - 1) : ' ';
                char c3 = s3.charAt(i + j - 1);

                f[i][j] = c1 == c3 && f[i - 1][j] || c2 == c3 && f[i][j - 1];
            }
        }
        return f[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

3、状态压缩

// 滚动数组，状态压缩。f[i][j] 只和前一层状态f[i - 1][j] 或者是上一个状态 f[i][j - 1];
    // 针对前一层状态，可滚动覆盖。
    public boolean isInterleave2(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), k = s3.length();

        if (m + n != k) return false;

        // 状态定义，f[i][j]表示s1[i-1]+s2[j-1]=s3[i+j-1]，s1第0-i个字符形成的字串+s2第0-j个字符形成的字串。
        boolean[] f = new boolean[n + 1];
        // 状态初始化，两个空字符成功交错成一个空字符。
        f[0] = true;
        // 状态转移
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == j && j == 0) continue;

                char c1 = i != 0 ? s1.charAt(i - 1) : ' ';
                char c2 = j != 0 ? s2.charAt(j - 1) : ' ';
                char c3 = s3.charAt(i + j - 1);

                f[j] = c1 == c3 && f[j] || c2 == c3 && f[j - 1];
            }
        }
        return f[n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结

1）匹配问题常常可dfs暴力匹配，如果字符稍长，就会出现timeout，可用动规进行时空中和。

2）动规的题要多练才会找到状态定义，没有题感就没有角度。秉持着将大问题转换为规模更小性质相同的子问题的原则。

参考文献

[1] LeetCode 交错字符串