Word Break | Leet code 139 | Theory explained + Python code

This video is a solution to Leet code 139, Word Break. I explain the question, go over how the logic / theory behind solving the question and finally solve it using Python code.
Comment below if you have a better solution to this problem!
Let me know if you have any feedback and don't forget to subscribe for more videos!
Code: leetcode.com/problems/word-br...)
More leetcode questions solved:
• Add and Search Word - ...
Timestamps:
0:00 Question
2:01 Solution Explained
9:34 Python Code
Gear used:
Mic: amzn.to/3awi3b6
Drawing pad: amzn.to/2O7PaaU

[@ujss2012]

I tried to follow Neetcode's explanation. But it seemed to me that he actually didn't fully understand it. Which is the case when you explain something but your code follows a different rationale. Thanks for sharing your understanding!

[@RobertPodosek]

For real, idk why he always tries to start from the end of the array.

[@j.a.s.o.n.z.h.a.n.g]

I literally watched like four DP explanations, finally clicked at yours!!

[@RobertPodosek]

I keep getting list index out of bounds on 'dp[indx - len(word)]'

[@weili5716]

Good explanation of the solution! Thank you

[@MahmudulHasan-nq4th]

Great explanation! Thank you.

[@arnabpersonal6729]

you can have a break inside the if statement too

[@tanvikhosla8084]

what is the time complexity of endswith?

[@tenzin8773]

Great video and explanation Anish! In terms of time complexity is it O(w*n) where "w" is the number of words in the wordDict and "n" is the length of the word?

[@bhargavsriram4737]

Thank you very much for a detailed solution

[@saianishmalla2646]

Happy to help!!

[@sharifmansuri607]

Superb solution.. Thanks for this video

[@saianishmalla2646]

Happy to help !!

[@padengg1053]

Thanks for this :D

[@saianishmalla2646]

No problem!

[@-SiddharthaChappidi]

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
matrix=["True"]+["False"]*len(s)
index=0
for i in range(0,len(s)):
word=s[index+1:i]
if word in wordDict:
matrix[i]="True"
index=i
else:
matrix[i]="False"
return(matrix[-1])
bro its giving correct output in programiz,but wrongoutput in leetcode for the same test case:s="catsandog"
wordDict=["cats","dog","sand","and","cat"].can i know reason ?

[@VayunEkbote]

For all those getting list index out of range error, try this.
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [True] + [False] * len(s)

for i in range(1, len(s) + 1):

for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]

[@-Corvo_Attano]

*JAVA SOLUTION*
class Solution {
HashSet set = new HashSet();
public boolean wordBreak(String s, List wordDict) {
if(s.length() == 0) return true;
if(set.contains(s)) return false;
for(String str:wordDict){
if(s.indexOf(str) == 0){
if(wordBreak(s.substring(str.length()),wordDict)) return true;
}
}
set.add(s);
return false;
}
}