Date and Time: Jul 2, 2024, 16:01 (EST)
Link: https://leetcode.com/problems/word-break/
Example 4:
Input: s = "cars", wordDict = ["car", "ca", "rs"]
Output: true
Example 5:
Input: s = "aaaaaaa", wordDict = ["aaaa", "aaa"]
Output: true
Example 6:
Input: s = "goalspecial", wordDict = ["go", "goal", "goals", "special"]
Output: true
Edge Case:
Input: s = "abcd", wordDict = ["a","abc","b","cd"]
Output: true
We want to create dp = [False] * (len(s) + 1), and we want to check backward from s to see if each word in wordDict matches. We only need to check two things: 1. current index i + len(word) < len(s) + 1 (make sure in bound). 2. The word we check matches this current subarray in s.
If they match, we set dp[i] = dp[i+len(word)], and check if dp[i] is True, we can skip checking other words for current i, otherwise, we may find another word can be matched from index i, but that is not the correct word we should use. Check edge case.
Finally, return dp[0].
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# Q: Check if s can be segamented into wordDict
# S: Check each word backward from s, if word exists, set dp[i] to be dp[i+len(word)], finally check if dp[0] is True
# TC: O(n * m), n=len(s), m=len(wordDict), SC: O(n)
dp = [False] * len(s) + [True]
for i in range(len(s)-1, -1, -1):
# Check each word in wordDict, if s[i:i+len(word)] matches current word
for word in wordDict:
if i + len(word) < len(s)+1 and s[i:i+len(word)] == word:
dp[i] = dp[i+len(word)]
if dp[i]:
break
return dp[0]Time Complexity:
Space Complexity:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# Compare from 0 to end
dp = [True] + [False] * len(s)
for i in range(len(s)):
for word in wordDict:
if i + 1 - len(word) >= 0 and s[i+1-len(word):i+1] == word:
dp[i+1] = dp[i+1-len(word)]
if dp[i+1]:
break
return dp[-1]
