Word Break

medium1D Dynamic Programming84 stepsJava · Python · C++

Can the string be split into dictionary words? dp[i] is true if the first i characters can be split. dp[i] is true when some dp[j] is true and s[j..i) is a word.

▶ Watch the animated trace

Traced input: s = "leetcode", wordDict = [leet, code] → true. Original problem: neetcode.io/problems/word-break

Complexity

BestO(n²)

AverageO(n²·L)

WorstO(n²·L)

SpaceO(n)

n² (j, i) pairs, each with a substring lookup of length up to L.

Key idea

dp[0] = true: the empty prefix is always splittable.
For each end i, look for a split point j where the prefix works and the rest is a word.
Limiting j to the longest word length speeds it up.

Common mistakes

Greedy longest-match fails: "aaaaaaa" with ["aaaa", "aaa"].
Plain recursion without memoisation is exponential.

Solution

Java

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> words = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && words.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

Python

def wordBreak(s: str, wordDict: List[str]) -> bool:
    words = set(wordDict)
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

C++

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1);
    dp[0] = true;
    for (size_t i = 1; i <= s.size(); i++) {
        for (size_t j = 0; j < i; j++) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Reuse a word "apple" is used twice.	`s = "applepenapple", wordDict = [apple, pen]`	`true`
Can't finish Every split leaves "og" or similar.	`s = "catsandog", wordDict = [cats, dog, sand, and, cat]`	`false`
Greedy trap Taking the longest word "goals" first leaves "pecial"; DP also tries "goal" + "special".	`s = "goalspecial", wordDict = [go, goal, goals, special]`	`true`