Word Break

medium
Dynamic ProgrammingStringDynamic ProgrammingHash Table

Given a string s and a list of strings wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. The same word in the dictionary may be reused multiple times in the segmentation.

Examples

Example 1

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

Example 2

  • Input: s = "applepenapple", wordDict = ["apple","pen"]
  • Output: true
  • Explanation: "applepenapple" can be segmented as "apple pen apple". Words can be reused.

Example 3

  • Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
  • Output: false
  • Explanation: No valid segmentation exists for "catsandog".

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.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

Try every possible prefix of the string. If a prefix exists in the dictionary, recursively check whether the remaining suffix can also be segmented. If we reach the end of the string, the segmentation is valid. Without memoization, this explores an exponential number of partitions due to overlapping subproblems.

Algorithm

  1. If the string is empty, return `true`.
  2. For each prefix of length 1 to `n`, check if it exists in the dictionary.
  3. If the prefix is a dictionary word, recursively check the remaining suffix.
  4. If any recursive call returns `true`, return `true`. Otherwise, return `false`.
TimeO(2^n) in the worst caseSpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return helper(s, dict, 0);
    }

    bool helper(string& s, unordered_set<string>& dict, int start) {
        if (start == s.size()) return true;
        for (int end = start + 1; end <= (int)s.size(); end++) {
            if (dict.count(s.substr(start, end - start)) && helper(s, dict, end)) {
                return true;
            }
        }
        return false;
    }
};
Java 21
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        return helper(s, dict, 0);
    }

    private boolean helper(String s, Set<String> dict, int start) {
        if (start == s.length()) return true;
        for (int end = start + 1; end <= s.length(); end++) {
            if (dict.contains(s.substring(start, end)) && helper(s, dict, end)) {
                return true;
            }
        }
        return false;
    }
}
Python 3.12
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)

        def helper(start: int) -> bool:
            if start == len(s):
                return True
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set and helper(end):
                    return True
            return False

        return helper(0)
Go 1.26
func wordBreak(s string, wordDict []string) bool {
    dict := make(map[string]bool)
    for _, w := range wordDict {
        dict[w] = true
    }
    var helper func(start int) bool
    helper = func(start int) bool {
        if start == len(s) {
            return true
        }
        for end := start + 1; end <= len(s); end++ {
            if dict[s[start:end]] && helper(end) {
                return true
            }
        }
        return false
    }
    return helper(0)
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

Define dp[i] as whether the substring s[0:i] can be segmented into dictionary words. For each position i, check all possible last words ending at i: if dp[j] is true and s[j:i] is in the dictionary, then dp[i] is true. Using a hash set for the dictionary gives O(1) lookups.

Algorithm

  1. Create a boolean array `dp` of size `n + 1`, with `dp[0] = true`.
  2. Put all dictionary words into a hash set.
  3. For each position `i` from 1 to `n`, check all `j` from 0 to `i - 1`:
  4. Return `dp[n]`.
TimeO(n^2 * k) where n is the string length and k is the average word length for substring comparisonSpaceO(n + m) where m is the total characters in wordDict

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};
Java 21
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
Python 3.12
from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[n]
Go 1.26
func wordBreak(s string, wordDict []string) bool {
    dict := make(map[string]bool)
    for _, w := range wordDict {
        dict[w] = true
    }
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && dict[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

Frequently asked questions

What is the optimal time complexity of Word Break?

The most efficient approach in this guide ("Dynamic Programming (Bottom-Up)") runs in O(n^2 * k) where n is the string length and k is the average word length for substring comparison time and uses O(n + m) where m is the total characters in wordDict extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Word Break use?

Word Break is a medium-level Dynamic Programming problem involving String, Dynamic Programming, Hash Table. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Word Break be solved without extra space?

The most space-efficient approach in this guide uses O(n + m) where m is the total characters in wordDict extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(n + m) where m is the total characters in wordDict.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
s=
"leetcode"
wordDict=
["leet","code"]
Expected Output
true