TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
- Check, for each index, whether the indices that came before it are in the dictionary.
- If you have leet, and l is not in the dictionary, then there is no point in segmenting as l and eet, respectively.
Complexity
Runtime
-
- N is the number of characters in a string
- K is the cost of string operations to get the prefix
- M is the amount of words in the wordDict.
- And so for each prefix, you perform string operations on that prefix for each word in the wordDict.
Space
- for the DP array storing whether the current size prefix can be filled
- plus for each cut of the prefixes (which gets reset, so we use only at any point.
Code
Bottom Up
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
prefix = s[:i + 1]
for word in wordDict:
if len(word) <= len(prefix):
cut = len(prefix) - len(word)
if dp[cut] and word == prefix[cut:]:
dp[i + 1] = True
break
return dp[n]Top Down
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@cache
def r(i):
if i <= 0:
return True
for word in wordDict:
# ex) hello, i = 5, word = llo: s[5 - 3:5] => [2:4] = llo
if word == s[i - len(word):i] and r(i - len(word)):
return True
return False
return r(len(s))- Top in this case is the total string, which came from postfixes making up that string.
Notes
Cards
START Basic Front: Word Break Back: For each prefix, calculate whether any word in wordDict can fill up the prefix given previously filled up prefixes.
END