Interleaving String

Interleaving String

Description:

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.

分析：

动态规划，下面给出证明。

  1. 最优子结构。

  2. 重叠子问题。

因为只涉及两个string之间的状态转换，所以是个二维dp，关键是如何得到递推关系。

可以假设dp[i][j]是s1的第前i个字母和s2的前j个字母相interleaving能否组成s3。dp[i][j]可以由两个状态得到：dp[i-1][j]、dp[i][j-1]，所以需要分两种情况（注意不能由dp[i-1][j-1]得到，因为s3需要由s1和s2组合得到，所以不能一下子跳2步）：

  1. dp[i][j]可以由状态dp[i-1][j]得到。此时case1 = dp[i-1][j] && s1[i-1] == s3[i+j-1]。

  2. dp[i][j]可以由状态dp[i][j-1]得到。此时case2 = dp[i][j-1] && s2[j-1] == s3[i+j-1]。

  3. dp[i][j]由case1与case2的||得到。

有了状态转换式，代码就很容易了。

代码如下：

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
class Solution {
public:
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true of false.
     * @date: 2016-12-19
     * dfs can also be applied.
     */
    bool isInterleave(string s1, string s2, string s3) {
        // write your code here
        int len1 = s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if (s3.size() != s1.size() + s2.size()) return false;
        
        vector<vector<bool> > dp(len1+1, vector<bool>(len2+1, true));
        
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1];
        }
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1];
        }
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                bool case1 = dp[i-1][j] && s1[i-1] == s3[i+j-1];
                bool case2 = dp[i][j-1] && s2[j-1] == s3[i+j-1];
                dp[i][j] = case1 || case2;
            }
        }
        
        return dp[len1][len2];
    }
};