The problem
Given a string s and a list of words wordDict, return true if s can be split into a sequence of one or more dictionary words, each used as often as needed.
Examples
01
- Input
s = "leetcode", wordDict = ["leet", "code"]
- Output
true
02
- Input
s = "applepenapple", wordDict = ["apple", "pen"]
- Output
true
03
- Input
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
- Output
false
Constraints
- 1 ≤ s.length ≤ 300
- 1 ≤ wordDict.length ≤ 1000
- 1 ≤ wordDict[i].length ≤ 20
- Lowercase letters; the words are all different.
The idea
Let ok[i] say whether the first i characters can be split into words. ok[0] is true — nothing needs no words. The first i characters split if some word ends exactly at i and the part before it splits: ok[i] = ok[j] and s[j..i) is a word, for some j.
No word is longer than the longest in the dictionary, so only that many js need checking for each i. Put the words in a hash set so each check is one lookup.
- Time
- O(n · L · L) — n positions, L starting points each, and an L-letter substring to hash
- Space
- O(n + total letters in the dictionary)
Solution · every language run against every case
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) longest = max(map(len, words)) # ok[i]: can s[:i] be split into words? It can if some word ends at i and # the part before that word can be split too. ok = [True] + [False] * len(s) for i in range(1, len(s) + 1): for j in range(max(0, i - longest), i): # no word is longer than `longest` if ok[j] and s[j:i] in words: ok[i] = True break return ok[len(s)]