[LeetCode] Interleaving String [30]

题目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

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

原题链接（点我）

解题思路

交差字符串。给3个字符串s1, s2, s3，推断s3是不是由s1和s2组成的交叉字符串。
设s1长度为m, s2长度为n，推断 s3[0...m+n-1] 是不是由s1[0...m-1], s2[0...n-1]组成的交叉字符串，如果s1[m-1] == s3[m+n-1]，则仅仅需推断s3[0...m+n-2]是不是由s1[0...m-2], s2[0...n-1]组成的交叉字符串...，依次这样推断下去。从这能够总结，这个问题能够划分为比它小的问题，这里使用动态规划应该比較合适。
dp[i][j]：表示s3[i+j-1] 是不是 由s1[0...i-1], s2[0...j-1]组成的交叉字符串。
dp[i][j] = dp[i][j] || dp[i-1][j] ; (s1[i-1]==s3[i+j-1])
              dp[i][j] || dp[i][j-1] ; (s2[j-1]==s3[i+j-1])

代码实现

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int m = s1.size();
        int n = s2.size();
        if(n+m != s3.size()) return false;
        vector<vector<bool> > dp(m+1, vector<bool>(n+1, false));
        //初始化dp[i][0]
        for(int i=0;i<m; ++i){
            if(s1[i] == s3[i])
                dp[i+1][0] = true;
        }
        //初始化dp[0][i]
        for(int i=0; i<n; ++i){
            if(s2[i] == s3[i])
                dp[0][i+1] = true;
        }
        dp[0][0] = true;
        int k;
        for(int i=1; i<=m; ++i)
            for(int j=1; j<=n; ++j){
                k = i+j;
                if(s1[i-1] == s3[k-1])
                    dp[i][j] = dp[i][j] || dp[i-1][j];
                if(s2[j-1] == s3[k-1])
                    dp[i][j] = dp[i][j] || dp[i][j-1];
            }
        return dp[m][n];
    }
};