Interleaving String | Leetcode 97 | Dynamic Programming

Please like, share and subscribe if you found the video useful. Feel free to ask in comments section if you have any doubts. :)

#leetcode
#leetcodeJuneChallenge
#interviewpreparation
Interleaving String cpp

Checkout the series: 🔥🔥🔥
LIKE | SHARE | SUBSCRIBE 🔥🔥😊

[adanulabidin]

Found the best explanation for this problem after seeing 2-3 videos. Thank you and keep it up!

PS: You can combine the two if conditions into a single one like this :

#include <bits/stdc++.h>
using namespace std;

bool helper(const string &a, const string &b, const string &c, int i, int j, int k, vector<vector<int>>& dp){
//base case
if(i == a.size() and j == b.size() and k == c.size()) return true;

//memoization
if(dp[i][j] != -1) return dp[i][j];

//checking both possibilities
bool x = false, y = false;
if(i < a.size() and a[i] == c[k]) x = helper(a, b, c, i+1, j, k+1, dp);
if(j < b.size() and b[j] == c[k]) y = helper(a, b, c, i, j+1, k+1, dp);

//populating dp table
return dp[i][j] = x or y;
}

bool isInterleave(string a, string b, string c){
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, -1));
int i = 0, j = 0, k = 0;
return helper(a, b, c, i, j, k, dp);
}

[kartiksingh]

Type of vector here is vector<int> dp;
But we are assigning TRUE or FALSE to it in recursion, how does that work??

[Ayush_.]

Goood Explaination 👌✨
only one Doubt :
Didi recusrsive calls me changing variables 3 he (i, j, k) par aapne dp me 2D array ka use kiya he shirf (i, j) ke status ka track rakhne ke liye, kyo ??
K variable ka status track kyo nhi kr rhe ???

[mojojojo-kv]

didi tabulation bhi batao na aap, isme memoization se bss 10-15% ko beat kar paar rhe in time complexity

[chintanpatel]

Time complexity will be O(s1.len *s2.len ) and what will be space complexity ?

[KhemendraBhardwaj]

Great Content, thanks for the solution

[amanmishra]

beaware if you use i++ in place of i+1 then you are going to get a segmentation error

[SaikatSamanta-qf]

Mam Your Voice is too low it will be better if you fix this. Otherwise explanation is good 🥰

[LittleWheelsBigDream]

Ma'am can u plz complete this ma'am

[anglepriya]

How you record your videos..pls share.

[sakshi]

i dont think you need i, j, k on line 34