Kiểm tra chuỗi xen kẽ trong C++

Cho ba chuỗi s1, s2 và s3. Kiểm tra xem s3 có được hình thành bằng cách xen kẽ (interleaving) s1 và s2 hay không. Ví dụ: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" → kết quả là true.

Giải thuật

Sử dụng quy hoạch động với mảng 3 chiều:

• Định nghĩa phương thức solve(s1, s2, s3, dp, i, j, k).
• Nếu i = 0, j = 0, k = 0 → trả về true.
• Nếu dp[i][j][k] != -1 → trả về giá trị đã lưu.
• ans := false.
• Nếu i > 0 và k >= 0 và s1[i] == s3[k] → ans = solve(s1, s2, s3, dp, i - 1, j, k - 1).
• Nếu j > 0 và k >= 0 và s2[j] == s3[k] → ans = ans OR solve(s1, s2, s3, dp, i, j - 1, k - 1).
• Lưu dp[i][j][k] = ans và trả về.
• Từ main: thêm khoảng trắng đầu chuỗi, tạo mảng dp kích thước (n+1) x (m+1) x (o+1) điền -1, gọi solve(n, m, o).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(string s1, string s2, string s3, 
               vector< vector< vector<int> > >& dp, int i, int j, int k) {
        if(i == 0 && j == 0 && k == 0) return true;
        if(dp[i][j][k] != -1) return dp[i][j][k];
        bool ans = false;
        if(i > 0 && k >= 0 && s1[i] == s3[k]) {
            ans = solve(s1, s2, s3, dp, i - 1, j, k - 1);
        }
        if(j > 0 && k >= 0 && s2[j] == s3[k]) {
            ans |= solve(s1, s2, s3, dp, i, j - 1, k - 1);
        }
        return dp[i][j][k] = ans;
    }

    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.size();
        int m = s2.size();
        int o = s3.size();
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;
        vector< vector< vector<int> > > dp(n + 1, 
            vector< vector<int> >(m + 1, vector<int>(o + 1, -1)));
        return solve(s1, s2, s3, dp, n, m, o);
    }
};

int main() {
    Solution ob;
    cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
    return 0;
}

Đầu vào

"aabcc", "dbbca", "aadbbcbcac"

Đầu ra

1