मान लीजिए कि हमारे पास तीन तार 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, तो सही लौटें
-
अगर 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)
-
-
डीपी सेट करें [आई, जे, के]:=उत्तर
-
वापसी डीपी [i, जे, के]
-
मुख्य विधि से, निम्न कार्य करें -
-
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