首页 > 代码库 > 40. Interleaving String

40. Interleaving String

Interleaving String

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.

思想: 动态规划。

DP[i][j] = (DP[i-1][j] && s1[i-1] == s3[i+j-1]) || (DP[i][j-1] && s2[j-1] == s3[i+j-1]); 其中,i, j 分别为字符串 s1, s2 的当前长度。

方法一:

class Solution {public:    bool isInterleave(string s1, string s2, string s3) {        if(s1.size() + s2.size() != s3.size()) return false;        if(s1 == "") return s2 == s3;        if(s2 == "") return s1 == s3;        vector<vector<bool> > DP(s1.size()+1, vector<bool>(s2.size()+1, false));        DP[0][0] = true;        for(size_t i = 1; i <= s1.size(); ++i) {            DP[i][0] = (DP[i-1][0] && s1[i-1] == s3[i-1]);            for(size_t j = 1; j <= s2.size(); ++j) {                DP[0][j] = (DP[0][j-1] && s2[j-1] == s3[j-1]);                DP[i][j] = (DP[i-1][j] && s1[i-1] == s3[i+j-1]) || (DP[i][j-1] && s2[j-1] == s3[i+j-1]);            }        }        return DP[s1.size()][s2.size()];    }};

方法二: 进一步优化,空间复杂度, O(min(s1.size(), s2.size()));

class Solution {public:    bool isInterleave(string s1, string s2, string s3) {        if(s1.length() + s2.length() != s3.length()) return false;        if(s1 == "") return s2 == s3;        if(s2 == "") return s1 == s3;        if(s2.size() > s1.size()) s1.swap(s2); // make the sapce O(min(s1.size(), s2.size()));        vector<bool> DP(s2.size()+1);        for(size_t i = 0; i <= s1.size(); ++i) {            DP[0] = (!i || (DP[0] && s1[i-1] == s3[i-1]));            for(size_t j = 1; j <= s2.size(); ++j) {                DP[j] = (DP[j] && s1[i-1] == s3[i+j-1]) || (DP[j-1] && s2[j-1] == s3[i+j-1]);            }        }        return DP[s2.size()];    }};

 

40. Interleaving String