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!

More leetcode questions solved:

Timestamps:
0:00 Question
2:01 Solution Explained
9:34 Python Code

Gear used:

[ujss]

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!

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

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

[tanvikhosla]

what is the time complexity of endswith?

[RobertPodosek]

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

[weili]

Good explanation of the solution! Thank you

[arnabpersonal]

you can have a break inside the if statement too

[-SiddharthaChappidi]

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:

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 ?

[tenzin]

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?

[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]

[sharifmansuri]

Superb solution.. Thanks for this video

[bhargavsriram]

Thank you very much for a detailed solution

[-Corvo_Attano]

*JAVA SOLUTION*
class Solution {
HashSet<String> set = new HashSet<>();
public boolean wordBreak(String s, List<String> 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;
}
}