【Interleaving String】cpp

题目：

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.

代码：

“merge sort + stack”

        struct LastMatch{

            int i1;

            int i2;

            int i3;

            LastMatch(int i1, int i2, int i3): i1(i1), i2(i2), i3(i3){}

        };

        static bool isInterleave(string s1, string s2, string s3)

        {

            const int n1 = s1.size();

            const int n2 = s2.size();

            const int n3 = s3.size();

            if ( n1+n2 != n3 ) return false;

            stack<LastMatch> sta;

            int i1=,i2=,i3=;

            while ( i1<n1 || i2<n2 || i3<n3 )

            {

                if ( s1[i1]==s2[i2] && s2[i2]==s3[i3] ){

                    sta.push(LastMatch(i1,i2,i3));

                    i1++; i3++;

                }

                else if ( s1[i1]==s3[i3] ){

                    i1++; i3++;

                }

                else if ( s2[i2]==s3[i3] ){

                    i2++; i3++;

                }

                else if ( !sta.empty() ){

                    LastMatch lm = sta.top(); sta.pop();

                    i1 = lm.i1; i2 = lm.i2; i3 = lm.i3;

                    i2++; i3++;

                }

                else{

                    return false;

                }

            }

            return i1==n1 && i2==n2 && i3==n3;

        }

"dp"

class Solution {

public:

        bool isInterleave(string s1, string s2, string s3)

        {

            const int n1 = s1.size();

            const int n2 = s2.size();

            const int n3 = s3.size();

            if ( n1+n2 != n3 ) return false;

            vector<vector<bool> > dp(n1+, vector<bool>(n2+, false));

            dp[][] = true;

            // check s1 boundary

            for ( int i = ; i <= n1; ++i ){

                dp[i][] = s1[i-]==s3[i-] && dp[i-][];

            }

            // check s2 boundary

            for ( int i = ; i <= n2; ++i ){

                dp[][i] = s2[i-]==s3[i-] && dp[][i-];

            }

            // dp process

            for ( int i = ; i<=n1; ++i )

            {

                for ( int j = ; j<=n2; ++j )

                {

                    dp[i][j] = ( s1[i-]==s3[i+j-] && dp[i-][j] )

                    || ( s2[j-]==s3[i+j-] && dp[i][j-] );

                }

            }

            return dp[n1][n2];

        }

};

tips：

这道题第一版采用“merge sort + stack”，有一个大集合过不去，报超时（但即使跟可以AC的dp方法对比，“merge sort+stack”过这个大集合也仅仅慢了不到10%，在数量级上应该没有差别，时间复杂度都是O(n²)）

dp的解法是学习网上的解法，理解如下：

dp[i][j]表示s1[0~i-1]与s2[0~j-1]是否匹配s3[0~i+j-1]

因此为了方便，定义dp[n+1][m+1]，多一个维度，目的是保证从s1中取的个数从0到n都可以表示（s2同理）。

可以写出来dp的通项公式：

dp[i][j] = ( s1[i-1]==s3[i+j-1] && dp[i-1][j] ) || ( s2[j-1]==s3[i+j-1] && dp[i][j-1] )

表示s3第i+j个元素要么由s1匹配上，要么由s2匹配上。

最后返回dp[n1][n2]就是所需的结果。

整个dp的过程并不复杂，思考下如何得来的：

1. dp取两个维度是因为s1和s2两个变量

2. 之前自己思考dp的时候，考虑的是每个位置可以由s1或者s2其中的元素表示，但是这样考虑起来就太复杂了；网上的思路并么有考虑到这么复杂，而是仅仅考虑s3中总共就这么长字符串，某个长度的字符串可以从s1和s2各取几个。

============================================

上述的dp过程的空间复杂度是O(n²)的，再采用滚动数组方式，把空间复杂度降低到O(n)，代码如下：

class Solution {

public:

        bool isInterleave(string s1, string s2, string s3)

        {

            const int n1 = s1.size();

            const int n2 = s2.size();

            const int n3 = s3.size();

            if ( n1+n2 != n3 ) return false;

            vector<bool> dp(n2+, false);

            // check s2 boundary

            dp[] = true;

            for ( int i = ; i<=n2; ++i )

            {

                dp[i] = s2[i-]==s3[i-] && dp[i-];

            }

            // dp process

            for ( int i = ; i<=n1; ++i )

            {

                dp[] = s1[i-]==s3[i-] && dp[];

                for ( int j = ; j<=n2; ++j )

                {

                    dp[j] = ( s1[i-]==s3[i+j-] && dp[j] ) || ( s2[j-]==s3[i+j-] && dp[j-] );

                }

            }

            return dp[n2];

        }

};

tips：如果二维的dp过程只跟紧上一次的dp过程有关，就可以退化为滚动数组形式的一维dp过程。

=======================================

第二次过这道题，参照dp的思路写了一遍。有个细节就是dp递推公式的时候“s3[i+j-1]”不要写成s3[i-1]或者s3[j-1]。

class Solution {

public:

    bool isInterleave(string s1, string s2, string s3) {

            if ( (s1.size()+s2.size())!=s3.size() ) return false;

            bool dp[s1.size()+][s2.size()+];

            fill_n(&dp[][], (s1.size()+)*(s2.size()+), false);

            dp[][] = true;

            for ( int i=; i<=s1.size(); ++i )

            {

                dp[i][] = dp[i-][] && s1[i-]==s3[i-];

            }

            for ( int i=; i<=s2.size(); ++i )

            {

                dp[][i] = dp[][i-] && s2[i-]==s3[i-];

            }

            for ( int i=; i<=s1.size(); ++i )

            {

                for ( int j=; j<=s2.size(); ++j )

                {

                    dp[i][j] = ( dp[i-][j] && s1[i-]==s3[i+j-] ) ||

                               ( dp[i][j-] && s2[j-]==s3[i+j-] );

                }

            }

            return dp[s1.size()][s2.size()];

    }

};

巴特西

【Interleaving String】cpp

最新文章

热门文章