Word Break

Problem Description

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.

Examples

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.

Verifying Reachability with Substring Partition Checks

A naive approach would recursively try to match words from the dictionary starting at index 0. If the input is "aaaaaaaaaaaaaaaaaaaaaaaaab" and the dictionary contains "a", "aa", "aaa", this recursive search branches exponentially before failing at the last character, resulting in a Time Limit Exceeded (TLE) error.

To solve this efficiently, we use dynamic programming to cache match results. Let dp[i] be a boolean indicating if the prefix s[0..i-1] can be segmented into dictionary words.

• The base case is dp[0] = true (an empty string is reachable).
• To compute dp[i] for index i from 1 to s.length(), we look backwards at potential word matching boundaries. For each word in wordDict, if the word matches the suffix of the prefix ending at i (i.e., s[i - word.length()..i - 1]), then dp[i] = dp[i - word.length()].

This reduces the search to a simple loop.

Solution 1: Dynamic Programming (Bottom-Up Tabulation)

Maintain a boolean array dp where dp[i] represents if the prefix of length i is segmentable.

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // base case: empty string

        // load words into a set for O(1) length checks (optional, we can loop over dict)
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i - len >= 0 && dp[i - len]) {
                    // check if suffix matches the dictionary word
                    if (s.substring(i - len, i).equals(word)) {
                        dp[i] = true;
                        break; // found a match for this index, move to next
                    }
                }
            }
        }
        return dp[n];
    }
}

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True  # base case: empty string

        for i in range(1, n + 1):
            for word in wordDict:
                length = len(word)
                if i - length >= 0 and dp[i - length]:
                    # check if suffix matches the dictionary word
                    if s[i - length : i] == word:
                        dp[i] = True
                        break  # match found, move to next index

        return dp[n]

#include <string>
#include <vector>

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        int n = s.length();
        std::vector<bool> dp(n + 1, false);
        dp[0] = true; // base case: empty string

        for (int i = 1; i <= n; i++) {
            for (const std::string& word : wordDict) {
                int len = word.length();
                if (i - len >= 0 && dp[i - len]) {
                    // check if suffix matches the dictionary word
                    if (s.compare(i - len, len, word) == 0) {
                        dp[i] = true;
                        break; // match found, move to next index
                    }
                }
            }
        }
        return dp[n];
    }
};

Complexity Analysis:

• Time Complexity: O(n * w * m) where n is the length of string s, w is the number of words in the dictionary, and m is the average length of words in the dictionary. Slicing/comparing strings takes O(m) time.
• Space Complexity: O(n) to store the DP array.

Where it breaks: If the dictionary is extremely large (e.g. 10⁵ words), looping over the dictionary at each step becomes slow. In this case, storing the dictionary in a Trie and matching prefixes starting from index i is more efficient.

Common Mistakes

• Using substring index bounds incorrectly. In Java, substring(start, end) includes start but excludes end. For a suffix of length len ending at index i, the slice is s.substring(i - len, i).
• Not breaking the loop early on match. Once dp[i] is marked true, you do not need to evaluate the remaining words for this index. Skipping early returns speeds up the execution significantly.
• Not handling memoization in recursion. Writing recursive checks without caching results in exponential time complexity O(2^n).

Frequently Asked Questions

Can we solve this using a Trie to optimize dictionary searches? Yes. You can build a Trie from the dictionary words. During the DP traversal, instead of iterating over the dictionary, you trace paths down the Trie starting at index i. This reduces word matching checks to O(max_word_length).

What if the dictionary contains empty strings? The constraints guarantee that word lengths are at least 1, so you do not need to guard against zero-length infinite loops.

What does this problem test in interviews? It tests your ability to optimize backtracking search spaces using 1D dynamic programming tabulation.

← All Problems