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!
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]
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 ?
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?
![[Live] : ONE 169 วันนี้!! "อนาโตลี vs อูมาร์"](http://i.ytimg.com/vi/IK3YZVWuFJg/mqdefault.jpg)
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!
For real, idk why he always tries to start from the end of the array.
I literally watched like four DP explanations, finally clicked at yours!!
Great explanation! Thank you.
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]
Good explanation of the solution! Thank you
what is the time complexity of endswith?
I keep getting list index out of bounds on 'dp[indx - len(word)]'
you can have a break inside the if statement too
Thank you very much for a detailed solution
Happy to help!!
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 ?
Superb solution.. Thanks for this video
Happy to help !!
*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;
}
}
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?
Thanks for this :D
No problem!