Log inSign up
mediumleetcodeNot Started

Word Break

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on leetcode
Lesson

Problem Statement

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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: Cannot segment the entire string.

Constraints:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Design 1D prefix segmentation DP tables.
  • Prune search intervals using maximum dictionary word length.
  • Integrate Trie data structures for direct prefix character lookups.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partitioning a string into valid words from a dictionary.
  • Determining reachability through contiguous token concatenation.

Algorithmic Decision Tree:

  • Partitioning a string into valid words from a dictionary.
  • Determining reachability through contiguous token concatenation.

Connected Patterns:

Word Break IIConcatenated WordsPalindrome Partitioning

1. Memoized DFS Recursion

Intuition

Define canBreak(start) checking if s[start...] can be segmented. Base case: start == s.length returns true. For end from start + 1 to s.length: if s[start...end-1] is in dictionary and canBreak(end) is true, return true. Memoize memo[start].

When to apply: Basic top-down conceptual formulation.

Algorithm

  1. Initialize memo array of size s.length with -1.
  2. Helper dfs(start):
  3. If start == s.length: return true.
  4. If memo[start] != -1: return memo[start] == 1.
  5. For end from start + 1 to s.length:
  6. If dict.contains(s[start...end-1]) && dfs(end): memo[start] = 1; return true.
  7. memo[start] = 0; return false.

Memoized DFS Recursion

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: Initial call canBreak(start=0)
Visual state
Values and pointers at this exact step
array
S
l
e
e
t
c
o
d
e
0
↑ DFS: start=0
1
2
3
4
5
6
7
Variables at this step
start
0
triedPrefixes
["l","le","lee"]
Check / comparison
Search prefixes of 'leetcode' in wordDict: 'l', 'le', 'lee' not found.
Decision / next transition
Continue scanning prefixes from start=0.
Why this step matters

Observation: Initial call canBreak(start=0).

Decision: Test dictionary membership for candidate prefixes: 'l', 'le', 'lee' are not in dictionary.

Invariant: A valid segmentation requires every partitioned substring to exist in the dictionary.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5
6class Solution {
7 int memo[305];
8 bool dfs(int start, const std::string& s, const std::unordered_set<std::string>& dict) {
9 if (start == (int)s.size()) return true;
10 if (memo[start] != -1) return memo[start];
11
12 for (int end = start + 1; end <= (int)s.size(); ++end) {
13 std::string sub = s.substr(start, end - start);
14 if (dict.count(sub) && dfs(end, s, dict)) {
15 return memo[start] = 1;
16 }
17 }
18 return memo[start] = 0;
19 }
20public:
21 bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
22 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
23 for (int i = 0; i <= (int)s.size(); ++i) memo[i] = -1;
24 return dfs(0, s, dict);
25 }
26};
27
28int main() {
29 Solution sol;
30 std::vector<std::string> dict = {"leet", "code"};
31 std::cout << (sol.wordBreak("leetcode", dict) ? "true" : "false") << std::endl; // true
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2) — N subproblems, each checking up to N prefixes.
  • Space complexity: O(N)

Why Brute Force Doesn't Scale:

Forward Trie traversal from reachable indices eliminates redundant substring allocations.

1D boolean array + compact 26-ary Trie.

2. Bottom-Up 1D Dynamic Programming with MaxLen Pruning

Intuition

Find maxLen among words in wordDict. Initialize dp of size N + 1 with dp[0] = true. For each i from 1 to N: iterate j from i - 1 down to max(0, i - maxLen). If dp[j] is true and s[j...i-1] exists in wordDict, set dp[i] = true and break.

When to apply: Standard tabular DP solution.

Algorithm

  1. Initialize dict = Set(wordDict) and compute maxLen.
  2. dp = Array(n + 1).fill(false); dp[0] = true.
  3. For i from 1 to n:
  4. For j from i - 1 down to max(0, i - maxLen):
  5. If dp[j] && dict.contains(s[j...i-1]):
  6. dp[i] = true; break.
  7. Return dp[n].

Bottom-Up 1D Dynamic Programming with MaxLen Pruning

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: Construct boolean array dp[9]
Visual state
Values and pointers at this exact step
array
S
l
e
e
t
c
o
d
e
0
↑ dp[0] = true
1
2
3
4
5
6
7
Variables at this step
dp
[true,false,false,false,false,false,false,false,false]
Check / comparison
Initialize dp array of size N+1 = 9. dp[0] = true (empty string).
Decision / next transition
dp[i] represents whether s[0..i-1] can be segmented.
Why this step matters

Observation: Construct boolean array dp[9].

Decision: Base case: dp[0] = true. All other entries start as false.

Invariant: dp[i] is true if there exists some j < i such that dp[j] is true and s[j..i-1] is in the dictionary.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_set>
5#include <algorithm>
6
7class Solution {
8public:
9 bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
10 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
11 int maxLen = 0;
12 for (const auto& w : wordDict) maxLen = std::max(maxLen, (int)w.size());
13
14 int n = s.size();
15 std::vector<bool> dp(n + 1, false);
16 dp[0] = true;
17
18 for (int i = 1; i <= n; ++i) {
19 for (int j = i - 1; j >= std::max(0, i - maxLen); --j) {
20 if (dp[j] && dict.count(s.substr(j, i - j))) {
21 dp[i] = true;
22 break;
23 }
24 }
25 }
26 return dp[n];
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::string> dict = {"apple", "pen"};
33 std::cout << (sol.wordBreak("applepenapple", dict) ? "true" : "false") << std::endl; // true
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N * maxLen) — Inner loop runs at most maxLen <= 20 times for each of the N characters.
  • Space complexity: O(N + totalDictChars)

3. Trie-Accelerated Forward DP (Optimal)

Intuition

Insert all words of wordDict into a Trie. Maintain boolean array dp of size N + 1 with dp[0] = true. For each index i from 0 to N - 1: if dp[i] is true, start walking from the root of the Trie matching characters s[j] for j from i to N - 1. If a matching Trie node is missing, break early. Whenever a terminal node is reached (node.isWord), set dp[j + 1] = true. Return dp[N].

When to apply: The standard gold standard solution eliminating substring allocations.

Algorithm

  1. Construct Trie containing all wordDict words.
  2. dp = Array(n + 1).fill(false); dp[0] = true.
  3. For i from 0 to n - 1:
  4. If !dp[i]: continue.
  5. node = trie.root.
  6. For j from i to n - 1:
  7. idx = s[j] - 'a'.
  8. If !node.children[idx]: break.
  9. node = node.children[idx].
  10. If node.isEnd: dp[j + 1] = true.
  11. Return dp[n].

1D Dynamic Programming Boolean Reachability Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [l, e, e, t, c, o, d, e]
Current operationSTEP 1 OF 6
Observation: Initialize boolean DP array of size N + 1 = 9
Visual state
Values and pointers at this exact step
array
S
l
e
e
t
c
o
d
e
0
↑ dp[0] = true
1
2
3
4
5
6
7
Variables at this step
dp
[true,false,false,false,false,false,false,false,false]
baseCase
Empty prefix is valid
Why this step matters

Observation: Initialize boolean DP array of size N + 1 = 9. Base case: dp[0] = true.

Decision: Set dp[0] = true (empty prefix can always be segmented).

Invariant: dp[i] is true if prefix s[0..i-1] can be segmented into dictionary words.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5struct TrieNode {
6 TrieNode* children[26] = {nullptr};
7 bool isEnd = false;
8};
9
10class Solution {
11 TrieNode* root;
12 void insert(const std::string& word) {
13 TrieNode* node = root;
14 for (char c : word) {
15 int idx = c - 'a';
16 if (!node->children[idx]) node->children[idx] = new TrieNode();
17 node = node->children[idx];
18 }
19 node->isEnd = true;
20 }
21public:
22 bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
23 root = new TrieNode();
24 for (const auto& w : wordDict) insert(w);
25
26 int n = s.size();
27 std::vector<bool> dp(n + 1, false);
28 dp[0] = true;
29
30 for (int i = 0; i < n; ++i) {
31 if (!dp[i]) continue;
32 TrieNode* node = root;
33 for (int j = i; j < n; ++j) {
34 int idx = s[j] - 'a';
35 if (!node->children[idx]) break;
36 node = node->children[idx];
37 if (node->isEnd) {
38 dp[j + 1] = true;
39 }
40 }
41 }
42 return dp[n];
43 }
44};
45
46int main() {
47 Solution sol;
48 std::vector<std::string> dict = {"cats", "dog", "sand", "and", "cat"};
49 std::cout << (sol.wordBreak("catsandog", dict) ? "true" : "false") << std::endl; // false
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(N * maxLen + totalDictChars) — Trie traversal avoids string hashing and substring memory copying.
  • Space complexity: O(N + totalDictChars)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Recursion with MemoizationO(N^2)O(N)Evaluates only reachable subproblems.Recursion call stack overhead.
2.Bottom-Up 1D Dynamic Programming with MaxLen PruningO(N * maxLen)O(N)Extremely fast, tight inner loop, zero recursion.Requires hash set lookups.
3.Trie-Based Bottom-Up DP (Optimal for large dicts)OptimalO(N^2) or O(N * maxLen)O(totalDictChars)Prefix pruning without substring allocations or hash computations.Trie construction boilerplate.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Checking all possible substring prefixes up to length N without capping at max word length or using a Trie.

Pitfall 2:

Using a plain list for dictionary lookups causing O(M) lookup penalty per substring check.

Crucial Edge Cases to Validate:

  • Single character matching dictionary (s = a, wordDict = [a]): dp[0]=true -> node at a isEnd=true -> dp[1]=true, returns true.
  • Prefixes match partially but fail globally (s = catsandog, wordDict = [cats, dog, sand, and, cat]): dp[9] remains false, returns false.
  • Reusing the same word multiple times (s = aaaaaaa, wordDict = [aaaa, aaa]): dp state allows repeated transitions correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present both the 1D DP recurrence and the Trie-accelerated forward scan.
  2. Mention the maxLen pruning optimization as an immediate win.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does traversing the Trie from reachable dp[i] == true states reduce time complexity?

Back to DSA Sheet