C++ में इंटरलीविंग स्ट्रिंग

मान लीजिए हमारे पास तीन स्ट्रिंग्स s1, s2 और s3 हैं। फिर जांचें कि क्या s3, s1 और s2 को इंटरलीव करके बनाई गई है या नहीं। यदि स्ट्रिंग्स "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 := s1 का आकार, m := s2 का आकार, o := s3 का आकार
  • s1, s2, s3 के आगे एक खाली स्थान जोड़ें।
  • (n+1) x (m+1) x (o+1) आकार का एक ऐरे बनाएं, -1 से भरें।
  • solve(s1, s2, s3, dp, n, m, o) वापस करें

उदाहरण (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")); 
}

इनपुट

"aabcc", "dbbca", "aadbbcbcac"

आउटपुट

1