Giả sử chúng ta có ba chuỗi s1, s2 và s3. Sau đó kiểm tra xem s3 có được tạo thành bằng cách xen kẽ s1 và s2 hay không. Vì vậy, nếu các chuỗi là “aabcc”, s2 =“dbbca” và s3 là “aadbbcbcac”, thì kết quả sẽ là true.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy s1, s2, s3 và một dp mảng 3d, rồi đến i, j, k
-
nếu i =0 và j =0 và k =0, thì trả về true
-
nếu dp [i, j, k] không phải là -1, thì trả về dp [i, j, k]
-
ans:=false
-
nếu j> 0 và k> =0 và s2 [j] =s3 [k] thì
-
ans:=giải quyết (s1, s2, s3, dp, i - 1, j, k - 1)
-
-
nếu j> 0 và k> =0 và s2 [j] =s3 [k] thì
-
ans:=ans HOẶC giải quyết (s1, s2, s3, dp, i, j - 1, k - 1)
-
-
đặt dp [i, j, k]:=ans
-
trả về dp [i, j, k]
-
Từ phương thức chính, thực hiện như sau -
-
n:=kích thước của s1, m:=kích thước của s2, o:=kích thước của s3
-
Thêm một khoảng trống trước s1, s2, s3.
-
tạo một mảng có kích thước (n + 1) x (m + 1) x (o + 1), điền vào giá trị này bằng -1
-
trả về giải quyết (s1, s2, s3, dp, n, m, o)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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 );
}
};
main(){
Solution ob;
cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
} Đầu vào
"aabcc", "dbbca", "aadbbcbcac"
Đầu ra
1