Word Break - Dynamic Programming - Leetcode 139 - Python

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@sunilgadhetharia2926]

In Java same algo not working import java.util.*; class Solution { public boolean wordBreak(String s, List wordDict) { boolean[] dp = new boolean[s.length()+1]; Arrays.fill(dp, false); dp[s.length()] = true; System.out.println(Arrays.toString(dp)); for(int i = s.length(); i >= 0; i--) { for( String w: wordDict) { if( i + w.length()

[@xwu524]

@@sunilgadhetharia2926 you need to use equals in Java to compare strings s.substring(i, i + w.length()) == w should be s.substring(i, i + w.length()).equals(w) if you use equal, it is like comparing the pointers of the variables, not their contents

[@longchikanouo4905]

var findRepeatedDnaSequences = function(s) { let count={}; for(let left=0;left=2) res.push(k) } return res; };

[@Abhinav-eu5le]

@NeetCode can you explain the time complexity of the dp solution ?

[@jayendraawasthi2646]

In my opinion, even the first brute force approach will require backtracking. Assume the wordDict = ["l", "leet", "code"], s = "leetcode". So now if we start matching then the first character "l" will match with wordDict[0] and now we will start searching for remaining "eetcode" and we won't find a match which is wrong. Hence we will have to backtrack and select "leet" instead of "l" to start with.

[@danielpe8533]

exactly what I thought

[@dishant-gupta]

For eetcode dp[0+1] will be false so loop will continue until it finds leet where dp[0+4] was previously set true as code was found.

[@quirkyquester]

yep, i agree with you on this one, but it won't need backtracking, it can just be recursion. the time complexity will be pretty crazy. something like n^m, (more or less.)

[@tharunkumar8133]

Awesome Explanation. You are the only guy who explains DP solutions with ease. I'm slowly getting comfortable with DP just because of your tutorials. Thank you so much.!!!

[@johnbuhanan5857]

Doing great, soon you will be the first leetcoder to have a "teamblind 75" playlist!

[@erassylzh5658]

you mean a neetcoder 😃

[@Cld136]

Great job! Please do Word Break II as well. Curious to see if we can use the same bottom up dp approach to store all possible sentences.

[@davidbujosa]

def wordBreak(s: str, wordDict: List[str]) -> bool: # Convert the wordDict to a set for faster lookup wordSet = set(wordDict) # Create a dp array of size s + 1 dp = [False] * (len(s) + 1) # Set the first element of the dp array to True dp[0] = True # Iterate through the dp array Bottom Up for i in range(1, len(dp)): # Iterate through the dp array again for j in range(i): # If the dp[j] is True and the substring from j to i is in the wordSet if dp[j] and s[j:i] in wordSet: # Set the dp[i] to True dp[i] = True # Break out of the loop break # Return the last element of the dp array return dp[-1]

[@EmceeEdits]

i was confusion till i watched this back a few times, I finally get the idea of why you are doing it this way. THANK YOU!!!

[@dataman4503]

Super crisp explanation. I understand your videos in just 1 go. These days I am searching for 'Leetcode # neetcode' in YT. Thanks dude.

[@TaiChiSWAG]

same my thoughts

[@namankeshari7332]

same!!

[@leeroymlg4692]

typing "neetcode #" is easier 😄

[@chillegaming8250]

How do we decide whether to start the DP table from the end or from the start? Is there anything particular in this problem that made you think we have to start from dp[8] as the base case and not dp[0] for the word "neetcode"?

[@kipa_chu]

can start from anywhere, it doesn't matter

[@a544jh]

I came up with a recursive top-down solution, using the substrings as the keys in the dp cache. It seems to be pretty much equally efficient.

[@SakshamBhatla]

Complexity appears incorrect (for the brute force). Each time a word is encountered, we have to break into 2 subproblems - we can either take the word, or continue without it. So it's exponential (2^n)

[@toolworks]

It gets split into two substrings, but only the right side is a subproblem which continues splitting. The left substring just gets checked against the dictionary as is, and only when it is present do we take the right substring as a subproblem. So it isn't 2^N in brute force.

[@mandy1339]

@@toolworks It is 2^N. There's a proof in the discuss section in Leetcode Website for this problem

[@jacoballen6099]

@@mandy1339 It is not 2^n. You can make all substrings in O(n^2). You can make all sub sequences in O(2^n). This problem is not 2^n

[@ahmadx307]

@@jacoballen6099 You can certainly get all substrings in n^2. However, each time you will be comparing two substrings only, while the string can be formed of 3 or more words

[@calebhopkins7382]

These are the best leetcode videos, no doubt. Thank you for the consistent and clear explanations.

[@HalfJoked]

Nice. This is similar but just explicitly codes in how we're marking valid word breaks with 'True'. class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [False] * (len(s) + 1) dp[0] = True for i in range(1, len(s) + 1): for w in wordDict: if dp[i - len(w)] and s[i - len(w) : i] == w: dp[i] = True return dp[-1]

[@taroserigano6546]

Thanks this helped!

[@tb8588]

Hey correct me if I am wrong but the approach that you did would be O(n^2*m) since you are slicing the string s as well, if you were to slice from 0 to len(s), wouldn't that be running in O(n) time? so the outer for loop is O(n) then inside you iterate through the word dict which is O(m) then inside the word dictionary you are slicing the string with worst case slicing be O(n) => O(n*m*n). Does it sound correct with you?

[@misterimpulsism]

I think this is just O(n*m) because the description says that the max length of a word is 20 characters. This means that s[i:i+len(word)] is considered O(1) time.

[@govindsanap5217]

Adding following line at the start will improve total time required wordDict = set(wordDict) As there are so many duplicate words in some test cases

[@kockarthur7976]

It only slightly improves computation time. Doing this will change wordDict lookup from O(w) to O(1), where w is the size of our wordDict. However for this problem, 'w' is restricted between 1 and 12, so at worst wordDict lookup as a list will be O(12) = O(1). There are no duplicate words in the wordDict. This is specified in the problem statement.

[@polycrylate]

@@kockarthur7976 Odd because it says now word dict length is 1 to 1000, and that also means the initial proposition of neetcode of going over possible substrings O(n^2) which is actually O(nm) because the length bound on a dict word is 20 So the initial ends up with O(nm^2) vs. O(nwm) and m is much smaller than w Maybe they changed the question/tests recently?

[@americanonobrasil2128]

Amazing videos. You've changed how I understand and think through problems instead of just memorization... Thank you!!!!

[@anujchoudhary5645]

Neetcode you are god. The way you teach is next level. Harvard should hire you

[@vaibhavsh82]

I don't think solution will work for every case. What if the word dictionary for the same neetcode would be [nee, leet, code, ode, ne, etcode]. As you can see the word can be made from ne+etcode but the algo will look "code" and then rest of the "neet" or word break of neet. I think the problem is that once it find a smaller substring "code" in the word dic it stops looking for any super set eg "etcode" that could also be found in the dictionary. Is my understanding correct.

[@victoriac7257]

I was thinking about the exact same thing. like how this code can avoid that

[@joereeve2569]

If you use that as a test case in leetcode it works. Becuase j is starting at 0 every time, eventually i will be at s.length and j will be at 0. Then j will increment until it reaches "ne" which will be true since it's found in the dict. Then the next check will see that a substring from j-i is also found in the dict, "etcode", and will set the last value in the dp array to true. Remember it doesn't truly care about what words it has found so far, only if the last value in the dp array is true or not. The other words only serve as places that the algorithm can check against. You would be right if we were removing words from the dict as we found them in the string, but we're checking the whole dict every time and the algorithm checks every combination of substrings.

[@DarrienGlasser]

There are test cases for this in leetcode already.

[@jshpro3]

@@joereeve2569 The solution from the video does not pass on Leetcode, they must have fixed the test case. You state that it checks every word in the dictionary everytime, but we can see clearly in the code @neetcode provided he breaks the loop when a match is found. When I run this algorithm with this input: "cars" ["car","ca","rs"] it matches "rs" at index 2, then it gets down to index 0 and matches "car", which causes the test case to fail since the "r" cannot be used twice. He is not keeping track of the index that was last matched. If I modify his algorithm to keep track of that information, it passes the above test case, but then in turn fails on this test case: "aaaaaaa" ["aaaa","aaa"]

[@joereeve2569]

@@jshpro3 Hey Josh, I went and tested my algorithm again to see if it failed against the fixed test cases you mentioned and it still passed. It also returns true for both test cases you just described. It's been so long since I did this I can't remember if I followed this video exactly, but I'll paste my code (it's in kotlin) here for you to see. Let me know if I'm missing anything. class Solution { fun wordBreak(s: String, wordDict: List): Boolean { val dp = Array(s.length + 1) {false} dp[0] = true for (i in 0..s.length) { for (j in 0 until i) { if (dp[j] == true && wordDict.contains(s.substring(j until i))) { dp[i] = true break } } } return dp[s.length] } }

[@andrepinto7895]

There is no advantage in going from len(s) to 0 in this case. You can do exactly the same thing with normal iteration from 0 to len(s).

[@jacobcutts4099]

No because you set dp[i] = dp[i+lenW] so you need to calculate top down

[@ismann9148]

@@jacobcutts4099You can just return dp[len(s)-1] if starting from 0.

[@polycrylate]

Interestingly, looking at the bounds of the question they may have changed. Now the length of the string (n) is 300 No. of dict words is 1000 (w) Length of a dict word is 20 (m) This means the initial proposition of finding every substring O(n^2) which is actually O(nm) because you only need substring of length 1 to m vs. Going through every dict word at every index O(nw) Both also need an extra factor of m to actually check/get the substring but still technically the first (whilst also using a set) is technically better

[@chilly2171]

The brute force approach is 2^n , not n^2

[@soumikdc]

I think the runtime for brute-force without memoization would be O(2^n), not O(n^2). String search would cost another O(m).

[@another14edits74]

Does it matter if I solve a problem in Top-Down approach and not Bottom-Up approach in an interview if the approach is not specified by the interviewer?

[@fishraider7897]

Brilliant. Took me two days to understand this. One thing I do not get, how do we know for certain we do not need to compare all the words in the dictionary -- we return immediately from dp[i] break;

[@Su_Has]

I don't understand why we break it if dp[i] , what happens if two words match the suffix? PS: if anyone didnt understand like me ​ I think once we have dp[i] as True we dont need to check for rest of the words in wordDict since its anyways True, so its sort of a little optimization to break the for loop early

[@tonyiommisg]

Same. Trying to understand this part

[@Su_Has]

​@@tonyiommisg I think once we have dp[i] as True we dont need to check for rest of the words in wordDict since its anyways True, so its sort of a little optimization to break the for loop early

[@Su_Has]

Updated the main comment with the answer as well

[@sickboydroid]

okk I think no is taking about my apporoach. What i did was use a trie data structure which has EXTREMELY good lookup for word prefixes. Thus at the cost of some space, i was able to solve this problem in a very efficient way

[@DanielOchoa23]

Would a suffix trie also be a good solution here?

[@mostinho7]

5:30 what decision tree looks like and how we can cache it

[@nanzownzu]

You sir are a saviour, well explained and neat solution. The LeetCode solution isn't as clean as this IMO.

[@vijaybabaria3253]

your explanation clarifies all my doubts about the solution. Thanks for creating this awesome resource. btw what tool do you use to explain with free hand sketching in different colors, is it done through any specific software? thanks again

[@shengbinwang5892]

You're so smart, I learned a lot from your channel.

[@CreedWylder]

Potential reason to use a Trie: - narrow down the list of words to iterate over As the list of words is considerably small the optimization might be an overkill. However the case where a Trie would make perfect sense is if we were operating on the same set of words but checking different strings. Eg: wordDict = Entire english dictionary (approx. 700K words), checking multiple strings against the same dictionary.

[@allensu4222]

i hate this problem

[@sofyswork2647]

Wow!! Amazing explanation. Thank you so much! I learned a lot from your videos. You're a hero!! Please keep uploading these quality videos!

[@chaoticguud]

Not only we can break early, but we must break early. This is not just an optimization. Otherwise, test case: s = "abcd" and wordDict = ["a","abc","b","cd"] will fail. The reason is, once we find "a", (and i + len(word)) to be True, that is a path. But if we move on, and we find "abc", then i + len(word) for "abc" will have us be dependent on there being a "d" in the dictionary, which there isn't. So, it is important to stop as soon as we found a path out, and not do an exhaustive search.

[@hfchen5323]

the main thing that confused me was `dp[i] = dp[i+len(w)]`, but now i understand it: it's just: If the word at index i to i +len(w), matches with some word w in dictionary: --> Then the T/F of dp[i] degrades to/depends on the T/F of dp[i+len(w)]

[@timothypark5661]

Wouldn't the brute force approach mentioned in 1:26 not work in this test case: s = "catsanddog" wordDict = ["cats","cat","and","dog"]. The algorithm would recognize "cat" as being in wordDict and go straight to looking at "sanddog" which isn't a valid word from the wordDict. Instead, it should see "cats" and "anddog" as two separate subproblems. Is there a workaround for this edge case?

[@kewtomrao]

Amazing, no other video on youtube explains this as crisp!

[@MrMayank822]

Very nice explanation. I'm just confused with 1 thing how come time complexity is O( n^2 m) so ideally there are just 2 loops one iterates over input string and inner loop iterates over each dic word and does the comparison, so complexity should be O(nm) (n= len of string) (m = max length of word in dict). What am I missing here?

[@mvh996]

once u get a match with a dict word(which is O(m*n) ), u have to repeat the entire process again with the remaining part of the word. so n * (m*n).

[@DavidDLee]

4:25, actually the problem description says the opposite. wordDict is longer. 1

[@kaushik.aryan04]

wordsDict[i] matters in this case not worddict.length

[@无敌无敌是橙子]

Thanks！！You saved my day, i was struggling for many hours until i watched this video!

[@stith_pragya]

Thank You So Much NeetCode Brother...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@zaf1093]

Isn't the runtime of the DP solution still technically O(n * m * n), where n is length of s and m is length of wordDict

[@hwang1607]

Not sure if helpful but here is the solution flipped around so its top down, this might be even more confusing: class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [False] * (len(s) + 1) dp[0] = True for i in range(1, len(s)+1): for w in wordDict: if (i - len(w)) >= 0 and s[i - len(w): i] == w: dp[i] = dp[i - len(w)] if dp[i]: break return dp[len(s)]

[@beyzayildirim0]

Great explanation. I have one question, I still am not sure why for i in range(len(s)-1, -1, -1): for w in wordDict: has a time complexity O(n*m*n) where n=len(s) and m=len(wordDict). Why is it not O(n*m)?

[@wyatttowne9357]

Late response here, so you may have already figured it out (and I hope someone corrects me here if I am wrong): I believe that last n in the big O notation is because that is the time it takes to compare both strings against each other. Comparing strings is a linear time operation I believe. So when we are checking to see if one of the words in wordDict is contained within our input string s, its possible that the word in wordDict could potentially have the same length as s. So in the worst case if the word in wordDict does in fact have the same length as s, (and we are implying that n = s.length), then we are comparing two strings of length n against each other, which would equate to the last n you are seeing in the Big O notation. Because we could potentially be doing that computation/comparison n*m times. Hope that makes sense. :)

[@jorgegonzaloalfaro5378]

hey neetcode, in 4:32 you said the max size of word dictionary is smaller than max size of string. but i looks like its the opposite: from lc: 1

[@hoyinli7462]

i have the same question. the answer may not be a good answer

[@rahuljadhav7156]

Actually he meant to say that each word in wordDict is smaller than the string given. But he rather said wordDict

[@SOMESHKHANDELIA]

The logic can be implemented with a Trie. I passed 35/47 testcases with a Trie based solution. But then got a TLE. Then I added DP to my Trie based solution and passed all testcases with Time Complexity better than 70% solutions.

[@shutdown-r]

I actually did the same Trie based solution, interesting to see someone else try that too.

[@akshayaggarwal5925]

Had the same exact approach! (That test case with a series of 'a's and a trailing 'b' made me add the cache :D)

[@parvesh8227]

Can we use a Trie ro solve this, if we build a Trie from the word dict, the. Check and eliminate the chars from the given string where endofWord is true?

[@infiniteloop5449]

Good idea!

[@CrCr-cl4rk]

An optimization would be to first check if dp[i+len(w)] is true before you go the compare. This way you might save some time comparing strings that even if you find it much, you are going to put a false in dp[i]

[@bhumberg3243]

i think it is better taking first letter and size from the selected word of the dictionary ,then check the word in the string .. instead of checking all the strings of size n

[@lucamantova3070]

not necessarily. You can still hash the comparison...

[@yanxu9167]

Thank you for sharing. Could you please explain more about why dp[8] is True?

[@MegaJiggaa]

This is a bit late, but the point is that if you add the length of the string, in this case "code" from index 4, it should end up on length of the string. Meaning it's +1 greater than array. So it would be dp[4] is equal to dp[4+4] which is dp[8], our base case. so then we match dp[0] with neet which gets it's value from dp[4]

[@Akaash449]

Can you please help me understand something??. What if instead of "leet", the word in the dictionary was "eet", or "et ", and the same in case of "code ", like say "de", or, "ode"..? How would we approach then?

[@leewilson8786]

what if words in dict are of different lengths? would it help to sort array by length in that case?

[@anshumansinha5874]

If we start solving the problem from the first word then there’s no need of the cache step. One directly jumps to the 5th word and then solve the remaining recursively. Why force dp on this problem?

[@b9944236]

I can only come out with brute forced solution, and get stucked what should i cache to speed up, and you explained it in a clear way, thanks.

[@istvanszabo6875]

great video 1 note: you can also start from the beginning, you just need to slightly adjust the logic

[@jerrychan3055]

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) sizes = set([len(ele) for ele in words]) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(n): for size in sizes: if i + size

[@Lamya1111]

omg you are the best. my saviour. tears of joy. please always make these vids.

[@Techgether]

working the dp array from dp[8] down to dp[0] should be called as top down approach? but he said bottom up?

[@raminessalat9803]

Hi, I think the brute force complexities calculated in the first part of the video is not correct. It is going to be exponential. I think it is O(n^n) for the first brute force approach. The reason is that after finding the match of every possible sub-sequence in the dictionary (which takes n^2), you have to find a match for the remainder of the string (which again would take O(n^2)). So overall it takes O((n^2)^(n^2)) = O(n^n). thats what i think. and another sign that O(n^2) is just wrong is that the second brute force approach should intuitively take less time but according to your calculations, it took O(m*n^2) which is more than O(n^2)

[@allenlam5210]

top-down solution I made after watching this vid since bottom-up felt unintuitive for me. class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: dp = [False] * (len(s)+1) dp[0] = True for i in range(1,len(s)+1): for w in wordDict: if s[i-1:i-1+len(w)] == w and dp[i-1]: dp[i-1+len(w)] = True return dp[len(s)]

[@johannsebastianbach3411]

Why dont we put the wordDict into a set and get constant lookup? The question states that len(wordDict) > len(s), So isn’t it better to optimize for worddict lookup?

[@dARKf3n1Xx]

better approach for memoization is to start from beginning and check from a set of worddict

[@princeofexcess]

why not convert wordDict into a set first? are we trying to save memory ?

[@AmolGautam]

You are doing god's work here. Thank you.

[@buildsucceeded]

the best explanation, as always!

[@mythicalwraith7026]

Can we use a trie to speed up the string lookup?

[@MrVenona]

This is a great explanation - best I've seen. Thanks!

[@andyescapes]

can someone explain why we go backwards seems like quite the trend in Neetcodes DP solutions? couldnt we do this very similarly just from index 0?

[@NeetCode]

Yeah, most people usually start from i=0, that def works. I go backwards because it's closer to the drawing explanation.

[@andyescapes]

@@NeetCode thank you for replying absolute honour, your videos are a life saver for an aussie trying to get a grad job! did you prefer to start from i=0 when doing dp personally?

[@junyuchen6413]

Thank you for your explanation! Could you also make a video of Leetcode 140 Word Break II ?

[@HaindaviKoppuravuri]

Pls explain the time complexity of the dp as well.

[@ankitupadhyay918]

Bruteforce can be to check for each substring .

[@Chatbot121]

how is it a word dictionary? Isn't it a word list?

[@hwang1607]

thank you, i dont see how someone could do this without knowing the solution already

[@ashkan.arabim]

I mean I did it without checking the solution

[@hwang1607]

@@ashkan.arabim ok

[@PAIPENG-c2b]

still dont understand why cant we work forwardly

[@debabhishek]

any reason Tries can 't be used in this problem , apart from cost of building the Trie,, ,, I can see the code implementation trying to match word from last index , do we have any advantage in this approach over starting from the first index ?

[@tanishasingh8875]

hey for the word leetcode and wordDIct=[''lee","leat","leets","leet","code"] I think the approach will fail

[@mudit7394]

It shouldn't fail

[@quirkyquester]

beautiful solution! I got this in an interview, and wasn't able to come up with this solution, but i came up with trie solution. and brute force without memorization loll. not good.

[@NickDrian]

This guy loves iterating backwards when he could just iterate forwards. The problem is symmetrical meaning the result would be the same if all of the strings are reversed which implies that there is no reason to go backwards.

[@davendrabedwal830]

Whats the problem in this approach ?? bool wordBreak(string s, vector& wordDict) { int n=s.length(); vectorexist(n+1,false); string temp; for(int i=1;i

[@lucamantova3070]

good explanation. But you missed out the part where you determine this solution step by step. It basically came out of nowhere.

[@Allen-tu9eu]

Thank u. save my life at 11:56PM. so I can go to sleep now.

[@schwarzchauhan]

backtrack & caching were enough to get all test case passed 😎

[@yinglll7411]

Thank you! Awesome thinking here!

[@Christian-jq6er]

Is it actually necessary to do this in reverse?

[@Humon66]

@Joe Reeve Thank you, I looked at your Kotlin code and converted it to Python. class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: bool """ dp = [False for i in range(len(s)+1)] dp[0] = True for i in range(0,len(s)+1): for j in range(0,i): if dp[j] == True and s[j:i] in wordDict: dp[i] = True break return dp[len(s)] # wordBreak("neet",["neet","code"])

[@sarthaksingh9363]

To anyone who has confusion here, what I like to do is transform the solution into english (or whatever your comfortable language is). In the bottom up solution here, what we are basically doing is checking two things : 1) wherever we have reached, do we have enough space after our pointer that any word in wordDict can fit there. If yes, then is the word right next to our pointer the same word in wordDict? 2) If the answer for (1) is yes, then we know that from our current point, we have a word towards our right which exists in wordDict, great! But, can everything after our current pointer be found in the wordDict? So we check, can the word which starts just after our current word that we found (at i + len(word)) be found in the wordDict? if yes, then we put a TRUE on our current pointer as well, because we can split the string after our current pointer such that the words exist in wordDict. we continue this till the end and return dp[0], which basically states that everything after this point can be split such that all splitted words exist in wordDict. Hope this helps!

[@yatharthvyas]

Is it a good idea to further optimize this algorithm by using a hashmap of arrays to store the list of words hashed by the starting alphabet? This would reduce the search complexity

[@romo119]

you can use a trie

[@jared6976]

@NeetCode why is this O(n^3). 2 nested loops. Is s[i:i+len(w)] o(n) for some reason? Array access is o(1)

[@guynameddan427]

I was thinking the same. Isn't the substring operation constant time complexity?

[@dheerajbarik383]

@@guynameddan427 Comparing 2 strings in worst case will be O(n) time complexity. -> e.g here in the above example if the complete word "neetcode" itself is present in the wordDict.

[@davteje]

Superb! Thank you again for your videos!! Could you share what drawing tool do you use for your videos? It looks quite nice

[@javidabderezaei3632]

A rough memoization (cache) solution: class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: res = [False] memo = [True] * len(s) def dps(memo, idx): if idx >= len(s): res[0] = True return if idx < len(s) and memo[idx] == False: return counter = 0 for word in wordDict: if s[idx:idx + len(word)] == word: idx += len(word) dps(memo, idx) idx -= len(word) if s[idx:len(word)] != word: counter += 1 if counter == len(wordDict) and idx < len(s): memo[idx] = False dps(memo, 0) return res[0]

[@DesiRiderKK]

what do you use for writing on computer and drawing?

[@calvin_713]

The moment that I though I mastered DP, here comes this question.....

[@Hav0c1000]

It didn’t occur to me to try each word in the word dict. I was instead building a trie, and testing all prefixes. TLE!!! Suffering!!!

[@Oliver-Zen]

I have a question guys, why the brute-force time complexity is O(n^2) instead of O(2^n) 3:06

[@quirkyquester]

i think that solution could even possibly be something like n^m (more or less). imagine you have s as "aaaaaaaaaab", and list as [a,aa,aaa,aaaa,aaaaa, b,c,d,e,f,g,h,i,j,k,l,m,n, ....], what would be the time complexity for this one? if you break it down, each steps, you check if there's a match, we can use hashmap, that could be O(1). but you have to do it n^2 times to check all possible substring with the hashmap, and each time there's a match, you might have to do the n^2 time again, so there will be maximumly max(m, n) depth. each depth has n^2 times, that gives about n^(2*m) times. and the algorithm is probably a little faster than this, cos this is the time complexity if there's always a match we could possibly do. but yepp, worst scenario is probably something like this.

[@osinakayahifeanyi1537]

You are my leetcode jesus

[@noctua7771]

Very interesting solution. Great job!

[@MP-ny3ep]

Phenomenal explanation. Thank you

[@PrateekGole]

Brute force approach #1, greedy one, won't work for cases like dict= ["leaf", "leafy","am"] and s = "leafyam"

[@anshulagarwal6682]

Why does try approach not working in this question?

[@uniquename2386]

What's the time complexity for recursive approach with and without caching?

[@srinadhp]

Thank you so much. Your explanation was very helpful. I almost thought of giving up on this one; then saw your video.

[@JustinMoore-op9yk]

Can someone explain the time complexity of the DP problem to me? Where M = len(s) and N = len(wordDict), the time complexity would be O(M*N) correct? I see others saying it would be O(M*N^2) because of the list slicing. Is that or is that not true and why?