Word Break
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Can a string be split into a sequence of words that all belong to a dictionary (words may be reused)?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which positions can be "clean" cut points? Start with position 0.
- Hint 2For a position, test every earlier clean position as a possible start of the last word.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A sentence typed without spaces: "leetcode". Walking along, you mark each position where the text so far can be cut cleanly into words. The start is cleanly cut (nothing yet). At each new position ask: "is there an earlier marked position such that the letters between it and here form a dictionary word?" If yes, mark this position too. If the end of the text gets marked, the whole sentence can be cut.
- The obvious way
Try every way to split by recursion: exponential.
- The key insight
can_split[0] = True. For each end position 1..n, look for a start before it where can_split[start] is True and the text between start and end is in the dictionary; if found, can_split[end] = True. The answer is can_split[n].
- The algorithm
- can_split[0] = True.
- For each end: try every start before it.
- can_split[start] and the text in between is a word: mark end True.
- Return can_split[n].
Watch it run
Examples = "leetcode", words = ["leet", "code"]
Position 0 (before anything) is cleanly cut.
marked: 0
Where people slip
- Put the words in a set so each lookup is O(1) on average.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def word_break(s, word_dict):
words = set(word_dict)
can_split = [False] * (len(s) + 1) # can the first k letters be cut into words?
can_split[0] = True # nothing yet is cleanly cut
for end in range(1, len(s) + 1):
for start in range(end):
if can_split[start] and s[start:end] in words:
can_split[end] = True
break
return can_split[len(s)]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.