首页 > 代码库 > leetcode[97] Interleaving String

leetcode[97] Interleaving String

题目给定s1和s2两个串,判断是否能合并成s3.

如果s3是s1和s2按顺序取某些数做结合的,那么就是true。例如

s1 = “abc”,s2=“def”,那么s3=“abdefc” 先去s1前两个,再取s2,再取是第三个。所以是合法的。

Given s1s2s3, 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.

思路一:

利用递归。

class Solution {public:    bool isInterleave(string s1, string s2, string s3)     {        if (s1.size() == 0) return s2 == s3;        if (s2.size() == 0) return s1 == s3;        if (s1.size() + s2.size() != s3.size()) return false;                if (s1[0] == s3[0] && s1[0] != s2[0])            return isInterleave(s1.substr(1), s2, s3.substr(1));        else if (s2[0] == s3[0] && s1[0] != s2[0])            return isInterleave(s1, s2.substr(1), s3.substr(1));        else if (s1[0] == s3[0] && s1[0] == s2[0])            return isInterleave(s1, s2.substr(1), s3.substr(1)) || isInterleave(s1.substr(1), s2, s3.substr(1));        else             return false;    }};

Time Limited

然后就想用动态规划了,一开始我定义dp[i][j][k],表示s1的前i个和s2的前j个是否和s3的前k个匹配。bool型的。如下:

class Solution {public:    bool isInterleave(string s1, string s2, string s3)     {        int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();        if (len1 == 0) return s2 == s3;        if (len2 == 0) return s1 == s3;        if (len1 + len2 != len3) return false;        bool dp[len1+1][len2+1][len3+1];                for (int i = 1; i <= len3; ++i)        {            if (i <= len1)                dp[i][0][i] = s1[i-1] == s3[i-1];            if (i <= len2)                dp[0][i][i] = s2[i-1] == s3[i-1];        }                for (int i = 1; i <= len1; ++i)            for (int j = 1; j <= len2; ++j)            {                int k = i + j;                if (s1[i-1] == s3[k-1] && s1[i-1] != s2[j-1])                    dp[i][j][k] = dp[i-1][j][k-1];                else if (s2[j-1] == s3[k-1] && s1[i-1] != s2[j-1])                    dp[i][j][k] = dp[i][j-1][k-1];                else if (s1[i-1] == s2[j-1] && s1[i-1] == s3[k-1])                    dp[i][j][k] = (dp[i][j-1][k-1] || dp[i-1][j][k-1]);                else                     dp[i][j][k] = 0;                }        return dp[len1][len2][len3];    }};

后面觉得不要用三维可以,可以把dp的第三维度干掉。dp[i][j]就表示s1的前i个和s2的前j个是否和s3的前i+j个匹配

class Solution {public:    bool isInterleave(string s1, string s2, string s3)     {        int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();        if (len1 == 0) return s2 == s3;        if (len2 == 0) return s1 == s3;        if (len1 + len2 != len3) return false;        bool dp[len1+1][len2+1];                for (int i = 1; i <= len3; ++i)        {            if (i <= len1)                dp[i][0] = s1[i-1] == s3[i-1];            if (i <= len2)                dp[0][i] = s2[i-1] == s3[i-1];        }                for (int i = 1; i <= len1; ++i)            for (int j = 1; j <= len2; ++j)            {                int k = i + j;                if (s1[i-1] == s3[k-1] && s1[i-1] != s2[j-1])                    dp[i][j] = dp[i-1][j];                else if (s2[j-1] == s3[k-1] && s1[i-1] != s2[j-1])                    dp[i][j] = dp[i][j-1];                else if (s1[i-1] == s2[j-1] && s1[i-1] == s3[k-1])                    dp[i][j] = (dp[i][j-1] || dp[i-1][j]);                else                     dp[i][j] = 0;                }        return dp[len1][len2];    }};

里面直接用 bool dp[len][len]这是自C99来允许的。leetcode上也允许,我在codeblock上也行,但在vs上就不行了。java就不会有这样的问题。还有为了移植性还是不那样用吧。大不了用动态数组呗。

leetcode[97] Interleaving String