Word Break II
A hashtag lost its spaces: s is a run of lowercase letters, and wordDict lists the words you may use. Return every sentence you can make by putting single spaces into s so that each piece is one of those words. The pieces keep the order of the letters of s, a word may be used as often as you like, and the sentences may come back in any order. If no cut works, return an empty list. Limits: 1 <= s.length <= 60, 1 <= wordDict.length <= 1000, every word has 1 to 20 lowercase letters, and the words are all different. The sentences together never run past 100000 characters. Example: s = "sunsetbeach", wordDict = ["sun","set","sunset","beach"] => ["sun set beach", "sunset beach"]
You have a string with its spaces stripped out and a word list, and you want every way to cut it back into real words. Interviewers use it to see whether you notice what a plain search wastes: branches that run to the end of the string, hit a dead end, and redo the same work from the same spot. Don't let the Hard label scare you; once you see the repeated work, the rest follows. Expect strings up to 60 letters, up to 1,000 words of at most 20 letters, and at most 100,000 characters of answer.
Examples
You write
word_break_ii(s: str, word_dict: List[str])
Example 1
- Input
- s = "sunsetbeach", wordDict = ["sun","set","sunset","beach"]
- returns
- ["sun set beach","sunset beach"]
Example 2
- Input
- s = "sunsetbench", wordDict = ["sun","set","sunset","beach"]
- returns
- []
Save this for your laptop
The editor and Run need a bigger screen. The link opens Word Break II ready to code. It is free, and the editor needs no account.
The pattern behind it
Backtracking
I reach for it when
- The question asks for all combinations, permutations or placements.
- You make a choice, explore it, and may need to take it back.
Say this before you type. Say the choice, the stopping rule, and the earliest moment you can prune.
All 15 Backtracking problemsDynamic Programming
I reach for it when
- Brute force repeats the same subproblem.
- You are asked for a count, a minimum or a maximum.
Say this before you type. Say the state in one sentence, then say which smaller states it reads from.
All 37 Dynamic Programming problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.