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 (with no characters left over). The same word may be used any number of times.
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- All strings are lowercase English letters
- Words in wordDict are unique
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion tries every first word and recurses on the rest, which is exponential on inputs like "aaaa...ab". The repeated work is solving the same suffix again and again. State: dp[i] = whether s[0..i) can be segmented. Recurrence: dp[i] is true if there is some j < i with dp[j] true and s[j..i) in the dictionary. Base case: dp[0] = true (the empty prefix). Memoising the recursion on the start index gives the same O(n^2) bound; the bottom-up table avoids recursion depth issues. Limiting i - j to the longest word length makes it faster still.
Algorithm
- Put
wordDictin a hash set and note the maximum word lengthL. - Create
dpof sizen + 1withdp[0] = true. - For
ifrom 1 ton, tryjfromi - 1down tomax(0, i - L). - If
dp[j]is true ands[j:i]is in the set, setdp[i] = trueand stop trying. - Return
dp[n].
O(n * L * L) with substring hashing (L = longest word)Space: O(n + total dictionary size)class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) max_len = max(len(w) for w in wordDict) n = len(s) dp = [False] * (n + 1) # dp[i]: s[:i] can be split dp[0] = True for i in range(1, n + 1): for j in range(i - 1, max(0, i - max_len) - 1, -1): if dp[j] and s[j:i] in words: dp[i] = True break return dp[n]