【LeetCode】97. 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.

可以用递归做，每匹配s1或者s2中任意一个就递归下去。但是会超时。

因此考虑用动态规划做。

s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。

当s1到达第i个元素，s2到达第j个元素:

地图上往右一步就是s2[j-1]匹配s3[i+j-1]。

地图上往下一步就是s1[i-1]匹配s3[i+j-1]。

示例：s1="aa",s2="ab",s3="aaba"。标1的为可行。最终返回右下角。

0 a b

0 1 1 0

a 1 1 1

a 1 0 1

class Solution {

public:

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

        int m = s1.size();

        int n = s2.size();

        if(m+n != s3.size())

            return false;

        vector<vector<bool> > path(m+, vector<bool>(n+, false));

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

        {

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

            {

                if(i ==  && j == )

                // start

                    path[i][j] = true;

                else if(i == )

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

                else if(j == )

                    path[i][j] = path[i-][j] & (s1[i-]==s3[i-]);

                else

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

            }

        }

        return path[m][n];

    }

};

巴特西

【LeetCode】97. Interleaving String

最新文章

热门文章