ধরুন আমাদের তিনটি স্ট্রিং s1, s2 এবং s3 আছে। তারপর s1 এবং s2 কে ইন্টারলেভ করে s3 গঠিত হয়েছে কিনা তা পরীক্ষা করুন। তাই যদি স্ট্রিংগুলো হয় “aabcc”, s2 =“dbbca”, এবং s3 হয় “aadbbcbcac”, তাহলে ফলাফল সত্য হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামক একটি পদ্ধতির সংজ্ঞা দিন, এটি s1, s2, s3 এবং একটি 3d অ্যারে dp নেবে, তারপর i, j, k
-
যদি i =0 এবং j =0 এবং k =0 হয়, তাহলে true রিটার্ন করুন
-
যদি dp[i, j, k] -1 না হয়, তাহলে dp[i, j, k] ফেরত দিন
-
উত্তর :=মিথ্যা
-
যদি j> 0 এবং k>=0 এবং s2[j] =s3[k] হয়, তাহলে
-
উত্তর :=সমাধান (s1, s2, s3, dp, i – 1, j, k – 1)
-
-
যদি j> 0 এবং k>=0 এবং s2[j] =s3[k] হয়, তাহলে
-
উত্তর :=উত্তর বা সমাধান (s1, s2, s3, dp, i, j – 1, k – 1)
-
-
সেট dp[i, j, k] :=ans
-
dp[i, j, k]
ফেরত দিন -
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
n :=s1 এর আকার, m :=s2 এর আকার, o :=s3 এর আকার
-
s1, s2, s3 এর আগে একটি ফাঁকা স্থান যোগ করুন।
-
আকারের একটি অ্যারে তৈরি করুন (n + 1) x (m + 1) x (o + 1), এটি -1 দিয়ে পূরণ করুন
-
রিটার্ন সলভ (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 );
}
};
main(){
Solution ob;
cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
} ইনপুট
"aabcc", "dbbca", "aadbbcbcac"
আউটপুট
1
