Given a string s and a dictionary wordDict, return true if s can be split into a sequence of one or more dictionary words. Words may be reused any number of times.
Example
Input s = "leetcode", wordDict = ["leet","code"]
Output true
Key Pointers
dp[i] = True means the prefix s[0:i] can be fully segmented into dictionary words; the final answer is dp[len(s)].
dp[i] is True if some earlier split point j < i has dp[j] True and s[j:i] is itself a dictionary word — build dp left to right, each position only looking backward.
Putting wordDict in a set first makes each "is this substring a word" check O(1) instead of scanning the whole list.
Step-by-Step Analysis
Convert wordDict to a set for O(1) lookups.
Create dp, a boolean array of size len(s) + 1, with dp[0] = True (the empty prefix is trivially segmented).
For each end position i from 1 to len(s): for each start position j from 0 to i − 1, if dp[j] is True and s[j:i] is a dictionary word, set dp[i] = True and stop checking further j values for this i.
Return dp[len(s)].
Complexity
Time: O(n²) — Space: O(n)
Code
def wordBreak(s: str, wordDict: list[str]) -> bool:
words = set(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 words:
dp[i] = True
break
return dp[len(s)]
Code Explanation
How the solution above works, piece by piece.
dp[i] answers: can the first i characters be split into dictionary words? dp[0] = True (the empty prefix).
For each end i, try every split point j: if s[:j] can be split (dp[j]) and s[j:i] is a word, then s[:i] can be too.
break as soon as one split works.
The answer is dp[len(s)].
O(n²) substring checks (plus the cost of slicing), O(n) space.
Visual Walkthrough
Running it on s = "leetcode", wordDict = ["leet", "code"]:
dp[i] is true when some earlier split point j is true and s[j:i] is a dictionary word. dp[4] is true because of "leet", and dp[8] because dp[4] is true and "code" follows.