This problem follows the String DP pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.
dp[i] = true if s[0..j] is valid and s[j..i] is in dictionary, for some j.
dp[i] means 'can s[0:i] be segmented?' — you try every possible last word s[j:i] and check if the prefix s[0:j] was also valid.
dp = [false] * (len(s) + 1)
dp[0] = true
wordSet = set(wordDict)
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordSet:
dp[i] = true
break
return dp[len(s)]Practice Word Break and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.
Practice this problem