Leetcode 97题 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

1
2
3
4
示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
1
2
3
4
示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

题解

这个问题我开始想用双指针，但是出来的报错，后来发现有些例子的结果是错误的，因为双指针说白了就是个贪心的策略。

后来参考了leetcode的题解，发现用动态规划能获得正确的解，不会陷入贪心的错误解中。
我们设f(i,j)是第一个字符串的前i位和第二个字符串的前j位能不能交错组合成第三个字符串的前i+j位。
若s3[i+j]==s1[i],则f(i,j)=f(i-1,j)。
若s3[i+j]==s2[j],则f(i,j)=f(i,j-1)。
初始状态f(0,0)=true;
如果某一个状态下s3[i+j]!=s1[i]&&s3[i+j]!=s2[j],则有不同的字符串不可能组合成目标字符串。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        auto f = vector < vector <int> > (s1.size() + 1, vector <int> (s2.size() + 1, false));

        int n = s1.size(), m = s2.size(), t = s3.size();

        if (n + m != t) {
            return false;
        }

        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[i][j] |= (f[i - 1][j] && s1[i - 1] == s3[p]);
                }
                if (j > 0) {
                    f[i][j] |= (f[i][j - 1] && s2[j - 1] == s3[p]);
                }
            }
        }

        return f[n][m];
    }
};