Problem

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example
For s1 = "aabcc", s2 = "dbbca"

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

思路

• 为什么需要从暴力搜索想到动归?
  • 因为这类型的搜索类似一个组合问题, 即从m个character中抽出n个与目标匹配, 所以复杂度为O(2^n)
  • 因为存在overlap subproblem, 所以我们需要记录子状态.
  • 这时候我们需要知道子状态与父状态的关系式

• 匹配矩阵

  • state

    • 尝试dp[i][j][k]代表s1前i个字符和s2前j个字符是否能与s3前k个字符匹配

    • 仔细一想, i + j 和 k是有关系的

      • 如果, i + j != k, 那么dp[i][j][k] 肯定 == 0

      • 我们只需要 i + j == k 的状态. 那么只需要保留i 和 j便可

    • dp[i][j] 表示 s1前i个字符和s2前j个字符是否能交替组成s3的前 i + j个字符

  • initialize

    • 初始化第一行第一列, dp[0][0] = true, 只要前面没匹配上变成false, 那么后面全是false

  • function

    • l1, l2, l3 分别代表s1, s2, s3字符串的最后一位

    • 从最后一个字符开始着手,

      • if s3[l3] == s2[l2], dp[i][l2] = dp[i][l2 - 1]

      • if s3[l3] == s1[l1], dp[l1][j] = dp[l1 - 1][j]

  • answer

    • dp[l1][l2]

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();

        if (l1 + l2 != l3) {
            return false;
        }

        boolean[][] dp = new boolean[l1 + 1][l2 + 1];
        dp[0][0] = true;

        for (int i = 1; i <= l1; i++) {
            dp[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0];
        }
        for (int i = 1; i <= l2; i++) {
            dp[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1) && dp[0][i - 1];
        }

        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1)) && dp[i - 1][j] || 
                            (s2.charAt(j - 1) == s3.charAt(i + j - 1)) && dp[i][j - 1];
            }
        }

        return dp[l1][l2];
    }

滚动数组优化