97-interleaving-string.md

97. Interleaving String - 交错字符串

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

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

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

---

题目标签：String / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	1868 ms	864.3 KB

static auto _ = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    void backTracking(string& s1, string& s2, string& s3, int i1, int i2, int i3, int& ret) {
        // cout << "[In] " << i1 << ", " << i2 << ", " << i3 << endl;
        if (ret != -1) {
            return;
        }
        if (i3 == (int)s3.size()) {
            ret = (i1 == (int)s1.size()) && (i2 == (int)s2.size());
            return;
        }
        if (i1 < (int)s1.size() && s3[i3] == s1[i1]) {
            i1++;
            i3++;
            backTracking(s1, s2, s3, i1, i2, i3, ret);
            i1--;
            i3--;
        }
        if (i2 < (int)s2.size() && s3[i3] == s2[i2]) {
            i2++;
            i3++;
            backTracking(s1, s2, s3, i1, i2, i3, ret);
            i2--;
            i3--;
        }
        // cout << "[Out] " << i1 << ", " << i2 << ", " << i3 << endl;
    }

    bool isInterleave(string s1, string s2, string s3) {
        int ret = -1;
        backTracking(s1, s2, s3, 0, 0, 0, ret);
        // cout << "ret: " << ret << endl;
        return ret == 1;
    }
};