Word Break

Description

You are given a string s and a list of strings called wordDict (the dictionary). Your task is to determine whether the string s can be broken apart into one or more segments, where every segment is a word that exists in the dictionary.

Words from the dictionary may be reused any number of times in the segmentation. The segments must cover the entire string — no characters can be left over, and no characters can be skipped.

Return true if such a segmentation exists, and false otherwise.

Examples

Example 1

Input: s = "leetcode", wordDict = ["leet", "code"]

Output: true

Explanation: The string "leetcode" can be split into two segments: "leet" and "code". Both "leet" and "code" are present in the dictionary, so the entire string is covered. Therefore the answer is true.

Example 2

Input: s = "applepenapple", wordDict = ["apple", "pen"]

Output: true

Explanation: The string can be segmented as "apple" + "pen" + "apple". Notice that the word "apple" is reused twice, which is allowed. All three segments are valid dictionary words, so the answer is true.

Example 3

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

Output: false

Explanation: Although several prefixes of the string match dictionary words ("cat", "cats", "sand", "and"), there is no way to segment the entire string such that every piece is a dictionary word. For instance, "cats" + "and" leaves "og" which is not in the dictionary. Similarly, "cat" + "sand" leaves "og". No valid complete segmentation exists.

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

Editorial

Brute Force

Intuition

The most straightforward way to tackle this problem is to try every possible way of splitting the string. Starting from the beginning of the string, we look at every possible prefix. If a prefix matches a dictionary word, we recursively try to break the remaining suffix.

Think of it like reading a sentence in a foreign language where you have a pocket dictionary. You start at the first letter and try to match the longest or shortest word you know. If you find a match, you move past that word and try to read the rest. If you get stuck, you backtrack and try a different word at the earlier position.

This approach explores all possible segmentations using recursion. At each position in the string, we branch into multiple choices — one for each dictionary word that matches the current prefix. This naturally forms a recursion tree.

Step-by-Step Explanation

Let's trace through with s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]:

Step 1: Start at index 0. We try every prefix of s starting from position 0.

Step 2: Check prefix "c" (s[0..0]) — not in dictionary. Move on.

Step 3: Check prefix "ca" (s[0..1]) — not in dictionary. Move on.

Step 4: Check prefix "cat" (s[0..2]) — found in dictionary! Recurse on the remaining string "sandog" starting at index 3.

Step 5: Inside the recursive call for index 3, check prefix "s" — not found. Check "sa" — not found. Check "san" — not found. Check "sand" (s[3..6]) — found! Recurse on "og" starting at index 7.

Step 6: Inside the recursive call for index 7, check prefix "o" — not found. Check "og" — not found. We've exhausted all prefixes. Return false for index 7.

Step 7: Back at index 3, we already tried "sand". Continue: check "sando" — not found. Check "sandog" — not found. Return false for index 3 (via "cat" path).

Step 8: Back at index 0, try next prefix: "cats" (s[0..3]) — found! Recurse on "andog" starting at index 4.

Step 9: At index 4, check "a" — not found. Check "an" — not found. Check "and" (s[4..6]) — found! Recurse on "og" starting at index 7.

Step 10: At index 7, same as Step 6: "o" and "og" not found. Return false.

Step 11: Back at index 4, continue past "and": check "ando" — not found. Check "andog" — not found. Return false for index 4.

Step 12: Back at index 0, no more prefixes to try. Return false. The string cannot be segmented.

Word Break — Recursive Exploration of All Segmentations — Watch how the recursive brute force explores every possible prefix at each position, branching when a dictionary word is found and backtracking when no valid segmentation exists.

Algorithm

Define a recursive function wordBreak(index) that returns true if s[index..end] can be segmented into dictionary words
Base case: If index equals the length of s, return true (we've successfully segmented the entire string)
Try every possible prefix s[index..j] for j from index to len(s) - 1:
- If the prefix exists in the dictionary, recursively call wordBreak(j + 1)
- If the recursive call returns true, return true
If no prefix leads to a valid segmentation, return false

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        return solve(0, s, wordDict);
    }
    
    bool solve(int index, string& s, vector<string>& wordDict) {
        // Base case: entire string has been segmented
        if (index == s.size()) return true;
        
        string prefix = "";
        for (int j = index; j < s.size(); j++) {
            prefix += s[j];
            
            // Check if this prefix is a dictionary word
            bool found = false;
            for (auto& word : wordDict) {
                if (word == prefix) {
                    found = true;
                    break;
                }
            }
            
            // If prefix matches, try to segment the rest
            if (found && solve(j + 1, s, wordDict)) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        def solve(index: int) -> bool:
            # Base case: entire string segmented
            if index == len(s):
                return True
            
            # Try every prefix starting at index
            for j in range(index, len(s)):
                prefix = s[index:j + 1]
                
                if prefix in wordDict:
                    # Prefix matches, try to segment the rest
                    if solve(j + 1):
                        return True
            
            return False
        
        return solve(0)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return solve(0, s, wordDict);
    }
    
    private boolean solve(int index, String s, List<String> wordDict) {
        // Base case: entire string segmented
        if (index == s.length()) return true;
        
        // Try every prefix starting at index
        for (int j = index; j < s.length(); j++) {
            String prefix = s.substring(index, j + 1);
            
            if (wordDict.contains(prefix)) {
                // Prefix matches, try to segment the rest
                if (solve(j + 1, s, wordDict)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, every position in the string could be a valid split point, leading to 2^n possible segmentations to explore. At each of the n positions, we may branch into multiple recursive calls, and without memoization, the same subproblems are solved repeatedly.

Space Complexity: O(n)

The recursion stack can grow as deep as n (the length of the string), since each recursive call processes at least one character and advances the index. The space used is proportional to the maximum recursion depth.

Why This Approach Is Not Efficient

The recursive brute force has exponential time complexity O(2^n). With a string of length 300 (the maximum constraint), 2^300 is an astronomically large number — far beyond what any computer can handle.

The root cause of inefficiency is overlapping subproblems. Consider our trace: wordBreak(7) was called twice — once through the "cat" → "sand" path and once through the "cats" → "and" path. Both times, it recomputed the same answer (false). In pathological cases, the same index can be reached through exponentially many different paths, each triggering a full recomputation.

The key insight: the result of wordBreak(index) depends only on the value of index, not on how we arrived at it. If we remember (memoize) the result for each index after computing it once, we never recompute it. There are only n possible index values (0 to n-1), so memoization reduces the total work dramatically.

Better Approach - Recursion with Memoization

Intuition

The brute force wastes time by recomputing answers for the same starting index over and over. We can fix this by adding a memo table — a simple array where memo[i] stores the result of wordBreak(i) once we've computed it.

Before making a recursive call for index i, we first check the memo table. If we've already computed the answer for that index, we return it immediately. If not, we compute it, store it in the memo table, and then return it.

This is called top-down dynamic programming (or memoization). The recursive structure stays the same — we just avoid redundant work by caching results.

To further speed up the dictionary lookup, we store the dictionary words in a hash set. This turns each "is this prefix in the dictionary?" check from O(m) (scanning the list) to O(k) on average (hash lookup, where k is the word length).

Step-by-Step Explanation

Let's trace with s = "leetcode", wordDict = ["leet", "code"]:

Step 1: Initialize memo array of size 9 (length of s + 1), all set to -1 (uncomputed). Convert wordDict to a set for O(1) lookups.

Step 2: Call wordBreak(0). memo[0] = -1, so we compute it. Try prefixes from index 0.

Step 3: Try prefix "l" — not in set. Try "le" — not in set. Try "lee" — not in set.

Step 4: Try prefix "leet" — found in set! Recurse on wordBreak(4).

Step 5: Call wordBreak(4). memo[4] = -1, so compute it. Try prefixes from index 4.

Step 6: Try prefix "c" — not in set. Try "co" — not in set. Try "cod" — not in set.

Step 7: Try prefix "code" — found in set! Recurse on wordBreak(8).

Step 8: Call wordBreak(8). Index 8 equals the string length, so we hit the base case. Return true.

Step 9: wordBreak(8) returned true, so wordBreak(4) stores memo[4] = true and returns true.

Step 10: wordBreak(4) returned true, so wordBreak(0) stores memo[0] = true and returns true.

Result: The string "leetcode" can be segmented as "leet" + "code".

Word Break — Memoized Recursion on "leetcode" — Watch how memoization caches results for each index, preventing redundant recomputation. Each index is computed at most once.

Algorithm

Convert wordDict into a hash set for O(1) average-time lookups
Create a memo array of size n + 1, initialized to -1 (meaning uncomputed)
Define recursive function wordBreak(index):
- If index == len(s), return true (base case)
- If memo[index] != -1, return memo[index] (cached result)
- For each j from index to len(s) - 1:
  - Extract prefix s[index..j]
  - If prefix is in the word set and wordBreak(j + 1) returns true:
    - Set memo[index] = true and return true
- Set memo[index] = false and return false
Return wordBreak(0)

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<int> memo(n, -1);
        return solve(0, s, wordSet, memo);
    }
    
    bool solve(int index, string& s, unordered_set<string>& wordSet, vector<int>& memo) {
        if (index == s.size()) return true;
        if (memo[index] != -1) return memo[index];
        
        for (int j = index; j < s.size(); j++) {
            string prefix = s.substr(index, j - index + 1);
            if (wordSet.count(prefix) && solve(j + 1, s, wordSet, memo)) {
                return memo[index] = true;
            }
        }
        
        return memo[index] = false;
    }
};

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        memo = {}
        
        def solve(index: int) -> bool:
            if index == len(s):
                return True
            if index in memo:
                return memo[index]
            
            for j in range(index, len(s)):
                prefix = s[index:j + 1]
                if prefix in word_set and solve(j + 1):
                    memo[index] = True
                    return True
            
            memo[index] = False
            return False
        
        return solve(0)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int[] memo = new int[s.length()];
        Arrays.fill(memo, -1);
        return solve(0, s, wordSet, memo);
    }
    
    private boolean solve(int index, String s, Set<String> wordSet, int[] memo) {
        if (index == s.length()) return true;
        if (memo[index] != -1) return memo[index] == 1;
        
        for (int j = index; j < s.length(); j++) {
            String prefix = s.substring(index, j + 1);
            if (wordSet.contains(prefix) && solve(j + 1, s, wordSet, memo)) {
                memo[index] = 1;
                return true;
            }
        }
        
        memo[index] = 0;
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n² × k)

There are n unique subproblems (one for each starting index). For each subproblem, we try up to n prefixes, and each prefix lookup in the hash set takes O(k) time where k is the prefix length (for hashing). In practice, since dictionary word lengths are bounded by 20, the prefix length is capped, making the effective complexity closer to O(n × m × k) where m is the maximum word length.

Space Complexity: O(n + m)

The memo array uses O(n) space. The hash set stores all dictionary words, using O(m) total space where m is the total characters across all words. The recursion stack depth is at most O(n).

Why This Approach Is Not Efficient

The memoized approach is much better than brute force — it reduces exponential time to polynomial. However, it uses O(n) recursion stack space due to the top-down recursive calls. For n = 300, this isn't a practical concern, but the approach also involves substring creation at each step, which adds overhead.

More importantly, we can express the same logic without recursion at all, using a simple iterative loop. A bottom-up dynamic programming approach fills a table from left to right, eliminating recursion overhead entirely and making the solution cleaner and more space-efficient in terms of stack usage. The bottom-up approach also makes the state transitions more transparent and is generally preferred in interviews.

Optimal Approach - Bottom-Up Dynamic Programming

Intuition

Instead of thinking recursively (top-down), we can build the answer from the ground up. We define a boolean array dp where dp[i] means "the first i characters of the string can be segmented into valid dictionary words."

The base case is straightforward: dp[0] = true, because an empty prefix (zero characters) is trivially segmentable.

For each position i from 1 to n, we check: is there any position j (where 0 ≤ j < i) such that:

dp[j] is true (the first j characters can be segmented), AND
The substring s[j..i-1] is a dictionary word?

If such a j exists, then dp[i] = true — we can segment the first i characters by taking whatever segmentation works for the first j characters and appending the word s[j..i-1].

Think of it as building a bridge across a river, stone by stone. dp[0] is the starting shore. Each dictionary word is a stone that can span a certain distance. We try to place stones one by one, always starting from a position we've already reached, until we reach the far shore dp[n].

Step-by-Step Explanation

Let's trace with s = "leetcode", wordDict = ["leet", "code"]:

Step 1: Initialize dp array of size 9 (length + 1): dp = [true, false, false, false, false, false, false, false, false]. Convert wordDict to set {"leet", "code"}.

Step 2: i = 1. Check if any word in dictionary ends at position 1. For "leet" (length 4): start = 1 - 4 = -3 < 0, skip. For "code" (length 4): start = 1 - 4 = -3 < 0, skip. dp[1] stays false.

Step 3: i = 2. Same checks: start positions are negative. dp[2] stays false.

Step 4: i = 3. Same: start positions negative. dp[3] stays false.

Step 5: i = 4. For "leet" (length 4): start = 4 - 4 = 0. dp[0] is true. Check s[0..3] = "leet" == "leet"? Yes! Set dp[4] = true.

Step 6: i = 5. For "leet": start = 5 - 4 = 1, dp[1] is false, skip. For "code": start = 5 - 4 = 1, dp[1] is false, skip. dp[5] stays false.

Step 7: i = 6. For "leet": start = 2, dp[2] false. For "code": start = 2, dp[2] false. dp[6] stays false.

Step 8: i = 7. For "leet": start = 3, dp[3] false. For "code": start = 3, dp[3] false. dp[7] stays false.

Step 9: i = 8. For "leet": start = 4, dp[4] is true! Check s[4..7] = "code" == "leet"? No. For "code": start = 4, dp[4] is true! Check s[4..7] = "code" == "code"? Yes! Set dp[8] = true.

Step 10: Return dp[8] = true. The string can be segmented.

Word Break — Bottom-Up DP Table for "leetcode" — Watch how the DP table fills from left to right. dp[i] becomes true when we find a dictionary word ending at position i that starts from a previously reachable position.

Algorithm

Convert wordDict into a hash set for O(1) lookups
Create a boolean array dp of size n + 1, initialized to false
Set dp[0] = true (base case: empty prefix is valid)
For each position i from 1 to n:
- For each word w in the dictionary:
  - Compute start = i - len(w)
  - If start >= 0 AND dp[start] is true AND s[start..i-1] == w:
    - Set dp[i] = true and break (no need to check more words)
Return dp[n]

Code

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        
        for (int i = 1; i <= n; i++) {
            for (auto& word : wordDict) {
                int len = word.size();
                int start = i - len;
                if (start >= 0 && dp[start] && s.substr(start, len) == word) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        
        word_set = set(wordDict)
        
        for i in range(1, n + 1):
            for word in wordDict:
                start = i - len(word)
                if start >= 0 and dp[start] and s[start:i] == word:
                    dp[i] = True
                    break
        
        return dp[n]

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        
        Set<String> wordSet = new HashSet<>(wordDict);
        
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                int start = i - len;
                if (start >= 0 && dp[start] && s.substring(start, i).equals(word)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n × m × k)

We iterate through n positions in the DP table. For each position, we check up to m dictionary words. Each word comparison involves comparing up to k characters (where k is the maximum word length, bounded by 20). With n ≤ 300, m ≤ 1000, and k ≤ 20, the total operations are at most 300 × 1000 × 20 = 6,000,000, which is very efficient.

Space Complexity: O(n)

The DP array uses O(n + 1) space. The hash set for the dictionary uses O(total characters in dictionary) space. No recursion stack is needed since this is iterative.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Word Break

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Recursion with Memoization

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Bottom-Up Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis