97. Interleaving String *HARD* -- 判断s3是否为s1和s2交叉得到的字符串

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.

class Solution {

public:

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

        int l1 = s1.size(), l2 = s2.size(), i, j;

        if(l1 + l2 != s3.size())

            return false;

        vector<vector<bool>> isMatch(l1+, vector<bool>(l2+, false));

        isMatch[][] = true;

        for(i = ; i <= l1; i++)

        {

            if(s1[i-] == s3[i-])

                isMatch[i][] = true;

            else

                break;

        }

        for(i = ; i <= l2; i++)

        {

            if(s2[i-] == s3[i-])

                isMatch[][i] = true;

            else

                break;

        }

        for(i = ; i <= l1; i++)

        {

            for(j = ; j <= l2; j++)

            {

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

            }

        }

        return isMatch[l1][l2];

    }

};

Considering:

s1 = a1, a2 ........a(i-1), ai
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1), c(i+j)

Defined

match[i][j] means s1[0..i] and s2[0..j] is matched S3[0..i+j]

So, if ai == c(i+j), then match[i][j] = match[i-1][j], which means

s1 = a1, a2 ........a(i-1)
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1)

Same, if bj = c(i+j), then match[i][j] = match[i][j-1];

Formula:

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

Initialization:

i=0 && j=0, match[0][0] = true;

i=0, s3[j] == s2[j], match[0][j] |= match[0][j-1]
s3[j] != s2[j], match[0][j] = false;

j=0, s3[i] == s1[i], match[i][0] |= match[i-1][0]
s3[i] != s1[i], Match[i][0] = false;

巴特西

97. Interleaving String HARD -- 判断s3是否为s1和s2交叉得到的字符串

最新文章

热门文章