MediumLeetCode #139Dynamic Programming
Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Constraints
1 <= s.length <= 300, 1 <= wordDict.length <= 1000
Examples
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Solution Approach
DP where dp[i] = can form s[0..i-1]. Check all substrings ending at i.
Implementation
def wordBreak(s, wordDict):
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
word_set = set(wordDict)
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]Complexity Analysis
Time Complexity
O(n² * m)Space Complexity
O(n)Complexity
Time:O(n² * m)
Space:O(n)
Hints
- 1.dp[i] = can we break s[0:i]?
- 2.Check all possible last words
- 3.Use set for O(1) word lookup
Asked at
Google