ধরুন আমাদের তিনটি স্ট্রিং s1, s2 এবং s3 আছে। আমরা যাচাই করব s3 কি s1 এবং s2-এর ইন্টারলিভিং (interleaving) দির্ঘে গঠিত হয়েছে। যেমন, s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" হলে ফলাফল true হবে।
সমাধানের ধাপসমূহ:
solve() নামে একটি মেথড সংজ্ঞায়িত করুন যা s1, s2, s3, একটি 3D dp অ্যারে এবং i, j, k ইনডেক্স গ্রহণ করবে।
যদি i=0, j=0, k=0 হয়, তবে true রিটার্ন করুন।
যদি dp[i][j][k] != -1 হয়, তবে dp[i][j][k] রিটার্ন করুন।
ans := false
যদি i > 0 এবং k >= 0 এবং s1[i] == s3[k] হয়, তবে ans := solve(s1, s2, s3, dp, i-1, j, k-1)
যদি j > 0 এবং k >= 0 এবং s2[j] == s3[k] হয়, তবে ans := ans OR solve(s1, s2, s3, dp, i, j-1, k-1)
dp[i][j][k] := ans সেট করুন।
dp[i][j][k] রিটার্ন করুন।
মূল ফাংশন থেকে n, m, o হল s1, s2, s3-এর আকার। স্ট্রিংদের শুরুতে ব্ল্যাঙ্ক স্পেস যোগ করুন। (n+1)x(m+1)x(o+1) আকারের dp অ্যারে -1 দিয়ে ভরুন। solve(s1, s2, s3, dp, n, m, o) কল করুন।
উদাহরণ
#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;
}
ইনপুট
"aabcc", "dbbca", "aadbbcbcac"
আউটপুট
1
