Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Constraints:
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 5000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of lowercase English letters.
- 0 <= i <= wordDict.length - 1
Examples:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" can be segmented into "leet" and "code".
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" can be segmented into "apple", "pen", and "apple".
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: There is no way to segment "catsandog" into words in the dictionary.
Solutions
Dynamic Programming
The dynamic programming approach involves creating a boolean array dp where dp[i] is true if the substring s[0..i] can be segmented into words in the dictionary. We initialize dp[0] to true and then iterate over the string, checking for each substring if it can be segmented by checking all substrings ending at the current position.
def wordBreak(s, wordDict):
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]Follow-up:
How would you optimize the solution if the dictionary is very large?
