Leetcode Solution 139. Word break [Dynamic Programming]

My contact details

You can practice for coding interview from here

I am Mohammad Fraz , a final year Engineer at DTU and I create content for Coding and technical interviews for FAANG. I explain the intuition to solve Data Structure and Algorithm Questions from leetcode and other platforms. I also cover interview experiences for FAANG and other tech giants. You will also find lectures on the frequently asked interview questions.

#wordbreak #leetcodesolutions #dynamicprogramming

[rohitgarg]

It would be great if you could share the space and time complexity in your videos.

[abhiroopsingh]

Just writing the code without explaination and not intution also. This shows that you have just copied code from somewhere and written here.

[peregrine]

It's a lovely question. There are tons of topics you could explain from this code. But you skipped all those things. Without a good dry run how we will be able to get the explanation behind the code. @Fraz

[SanyamBanoni]

bro you have to more thorough with your explanation..
it looks like you are making videos for those who have already solved the problem and came here for quick revision of concepts

[omkarshendge]

Bro slow it down a bit kuch nai samjha ye! Har ek statement explain kro pls

[guess_ds]

Awesome video.
Very very helpful for me.
Keep it up 👍

[kSERITIKGupta]

Day 20: solved 2 medium and revised Word Break problem from this video.
Most of my got spent in my personal works only :(
Total: Leetcode: 92 GFG: 57

[whysrishti]

Following code works:
int help(int i, string s, set<string>&wordDict, vector<int>& dp){ //i denotes the index we are currently standing on

string temp;

if(i==s.size())return 1; //if you reach end then return 1

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

for(int j=i;j<s.size();j++){ //traverse string from ith position and add each char to temp
temp += s[j];
//search the temp in set
//if found
if(help(j+1, s, wordDict, dp)) return dp[i]=1;

}
}
return dp[i]=0;
}

int wordBreak(string s, vector<string> &wordDict) {
//code here
vector<int> dp(s.length()+1, -1);
set <string> st;
//memset(dp, -1, sizeof dp);

for(auto a:wordDict) st.insert(a);

//help fx returns true if it is possible to break string s such that the fragments are present inside wordDict
return help(0, s, st, dp);
}

[harshitgarg]

Can anyone please explain how are we writing the base condition in helper function.

[ayushgupta]

Sharing bottom up approach code
var wordBreak = function(s, wordDict) {
var set = new Set(wordDict);
var size = s.length;
var dp = [];
return wbb();

function wbb() {
dp[size] = true;
for (let i = size - 1; i >= 0; i--) {
let temp = "";
for (let j = i; j < size; j++) {
temp += s[j];
if (set.has(temp) && dp[j + 1] === true) {
dp[i] = true;
}
}
}
return Boolean(dp[0]) ;
}

};

[kirtanprajapati]

Awesome explanation bcs mostof log top down hi krate he but apne recursion, top down and bottom up sab mst krva diya thankyou so much brother

I've one que like I'm good in dsa and dev but my english is very very week so kya kru uski vajah se confidence hi nhi ata dar lgta he

[mihiradarsh]

class Solution {
private:
bool helper(string &s, unordered_set<string> &st, int indx, int n) {
if(indx >= n) return true;
string temp = "";
for(auto i = indx; i < s.length(); i++) {
temp += s[i];
if(st.find(temp) != st.end()) {
if(helper(s, st, i+1, n) == true)
return true;
}
}
return false;
}

bool helperMemo(string &s, unordered_set<string> &st, int indx, int n, vector<int> &dp) {
if(indx >= n) return true;
if(dp[indx] != -1) return dp[indx];
string temp = "";
for(auto i = indx; i < s.length(); i++) {
temp += s[i];
if(st.find(temp) != st.end()) {
if(helperMemo(s, st, i+1, n, dp) == true) {
return dp[indx] = true;
}
}
}
return dp[indx] = false;
}

bool helperTab(string &s, int n, unordered_set<string> &st, vector<int> &dp) {
dp[n] = 1;
for(int indx = n-1; indx >= 0; indx--) {
string temp = "";
for(auto i = indx; i < s.length(); i++) {
temp += s[i];
if(st.find(temp) != st.end() and dp[i+1]) {
dp[indx] = 1;
break;
}
}
}
return dp[0];
}



public:
bool wordBreak(string s, vector<string>& wordDict) {
if(s.length() == 0) return true;
unordered_set<string> st;
// vector<int> dpMemo(s.length(), -1);
vector<int> dpTab(s.length()+1, 0);
for(auto &x : wordDict) st.insert(x);

// return helper(s, st, 0, s.length());
// return helperMemo(s, st, 0, s.length(), dpMemo);
return helperTab(s, s.length(), st, dpTab);
}
};

[yourbestie]

Bro giving Leetcode weekly and biweekly contest regularly is enough to clear Online coding round

[aryanupadhyay]

i think that there is a problem with the solution in the test case :--
wordDict=[ 'aaaa', 'aaa' ],
in this testcase the given code gives false but it should be true ...

[BOSS-sww]

how easily you made this problem amazing fraz bhai

[satyareddy]

you have not explained clarity like striver

[anshumanrana]

Online Coding / Assessment ki playlist update krdo 😄

[AyushKumar-jujj]

brute force approach was good, dp was too hastily done. Didn't like the way you explained DP approach

[tech_wizard]

Please make a dedicated video on your review of DSA course of apna college YouTube channel, do you think it's enough to crack tech giant's for beginners