Word Break
Mediumdp[i] = can s[0..i) split into dictionary words
A sentence works if you can chop a real word off the front and the rest also works.
The idea
dp[i] is true if some word in the dictionary ends exactly at position i and the prefix before it is also breakable. Build up from dp[0] = true.
T
·
·
·
·
·
·
·
·
0
1
2
3
4
5
6
7
8
dict{leet, code}
Step 1 of 10. dp[i] = can "leetcode"[0..i) be cut into dictionary words? dp[0] = true (empty prefix). Values: T, ·, ·, ·, ·, ·, ·, ·, ·. dict {leet, code}.
1/10
Optimal
timeO(n²)spaceO(n)
Reachable split points.
1const dp = Array(n + 1).fill(false); dp[0] = true;2for (let i = 1; i <= n; i++)3 for (let j = 0; j < i; j++)4 if (dp[j] && dict.has(s.slice(j, i))) { dp[i] = true; break; }5return dp[n];Input
- array
- [T, ·, ·, ·, ·, ·, ·, ·, ·]
Memory
- i
- —
- j
- —
- dict
- {leet, code}
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "leetcode", words = ["leet","code"]
- Output:
- true
- Explanation:
- Splits into leet + code.
Example 2
- Input:
- s = "applepenapple", words = ["apple","pen"]
- Output:
- true
- Explanation:
- apple + pen + apple.
Example 3
- Input:
- s = "catsandog", words = ["cats","dog","sand","and","cat"]
- Output:
- false
- Explanation:
- No clean split → false.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.