Word Break | Leetcode | Medium | Java | Striver's A to Z DSA Sheet | Recursion

[@atulwadhwa192]

Thanks for the video Aditi, because of your video I realised why it's a dp problem and more importantly how we can optimize it.
1-D dp solution [C++] [Memoization]
class Solution{
private:
bool solve(int ind,string &s,int str_len,unordered_map &mp,vector &dp){
if(ind==str_len)
return true;

if(dp[ind]!=-1)
return dp[ind];

for(int i=ind;i

[@algorithmsbyaditi]

great work !

[@ashuyadav2844]

hello Aditi, here is c++ code with 2D dp
note: s.substr(start,length): this function take length instead of end in c++,
class Solution {
public:
bool solve(int start ,int end,string &s,set &wD,vector &dp){
if(dp[start][end]!=-1){
return dp[start][end]==1 ?true:false;
}
if(end==s.length()-1){
if(wD.contains(s.substr(start,end - start + 1))){
dp[start][end] = 1;
return true;
}
return false;
}
if(wD.contains(s.substr(start,end - start + 1))){
if(solve(end+1,end+1,s,wD,dp)) {
dp[start][end]=1;
return true;
}
}
bool ans=solve(start,end+1,s,wD,dp);
dp[start][end]= ans ? 1:0;
return ans;
}
bool wordBreak(string s, vector& wordDict) {
setwd(wordDict.begin(), wordDict.end());
vector dp(s.length(), vector(s.length(), -1));
return solve(0,0,s,wd,dp);
}
};

[@aditipatil9491]

make more vdios youur explanation is amazing

[@algorithmsbyaditi]

Thank you, I will

[@Manpreetkaur-xr7cg]

one side of tree(0,6) returns false and other (5,9) returns true , which one will be considered

[@ChaithanyaGanesh_India]

class Solution {
public boolean wordBreak(String s, List wordDict) {
int [][]dp= new int [s.length()][s.length()];
for(int i=0;i= s.length()) {
return false;
}
if(dp[start][end]!=-1){
return dp[start][end]==1;
}

if(wd.contains(s.substring(start, end+1))){
if(end==s.length()-1 || fns(end+1, end+1, s, wd,dp)){
dp[start][end]=1;
return true;
}
}
boolean ans=fns(start, end+1, s, wd,dp);

dp[start][end]=ans? 1:0;
return ans;
}
}

[@ritikshandilya7075]

Amazing solution , Thanks for making this video

[@saurabhrthakur]

Hey Aditi I am getting problem in this, because public function is taking vector as argument , and we are giving 'set' in the private function

[@algorithmsbyaditi]

Yes, please create a set and add all the values of this vector to the set.

[@saurabhrthakur]

@@algorithmsbyaditi Bro, I have just sent you a connection request, so that i can ask my doubt there if would help me.

[@theashutoshgupta_yt]

why dont we take "wordDict" and traverse them to from "string s" like leet+code = leetcode, apple+dogs+apple =appledogapple, since this was in recursion section i avoided going in DP here.
droping the code here, review it as it is giving TLE after 32/46 testcases
class Solution {
private:
bool flag = false;
void solve(vector& wordDict, int index, string st, string temp){
// cout

[@samrat_malisetti]

I have gone through several videos about this problem. But I didn't find the solution that you explained. Great video :)

[@algorithmsbyaditi]

Glad it helped!

[@samrat_malisetti]

@@algorithmsbyaditi Can you share your approach for Longest Palindrome Substring?? With the similar approach !!!
Thank you

[@algorithmsbyaditi]

I solved that using two pointers. For solution please reach out on [e-mail]

[@ultimatescience3842]

Hey!
I am in my third year and still don't have any idea about coding.
I am thinking of doing DSA with c++ but don't know where and how to start. Also, striver's DSA playlist is not complete.
Can you please guide me?
I am planning and trying to get off-campus placement in a product-based company.

[@algorithmsbyaditi]

Yes, you can connect with me on LinkedIn(Aditi Chourasia). I will surely try to guide you with the best of my knowledge.