139. Word Break - Solution & Explanation

Q: Is Word Break easy or hard?

Word Break is considered a medium difficulty problem. The challenge is recognizing that brute-force recursion leads to exponential complexity and converting that idea into dynamic programming or memoization.

Q: How to solve Word Break in O(n)?

A strict O(n) solution is generally not achievable because every position may need to check multiple earlier split points. The practical optimal solution is O(n^2) using dynamic programming or DFS with memoization and a hash set for dictionary lookups.

Q: What is the best approach for Word Break?

The dynamic programming approach is the most common solution. Use a boolean DP array where dp[i] represents whether the prefix ending at index i can be segmented using dictionary words. With a hash set for fast lookups, the algorithm runs in O(n^2) time and O(n) space.

Q: What data structure is used in Word Break?

The solution typically uses a hash set to store dictionary words for O(1) membership checks and a dynamic programming array to track valid segmentations. Some optimized implementations also use a Trie to speed up prefix matching.

Q: What is the time complexity of Word Break?

Both the optimized dynamic programming and memoized DFS solutions typically run in O(n^2) time, where n is the string length. Each position checks earlier split points and performs constant-time dictionary lookups using a hash set. Space complexity is O(n) for the DP array or memo cache.

Q: Word Break Python or Java solution approach?

Python and Java implementations usually follow the same dynamic programming pattern: convert the dictionary to a set, iterate through string indices, and check valid split points. Both achieve O(n^2) time and O(n) space complexity.

Q: Is Word Break asked at Google or Amazon interviews?

Word Break is a classic dynamic programming interview problem and appears frequently in coding interviews at companies like Amazon, Google, and Meta. Variants include returning all valid sentences (Word Break II) or optimizing with a Trie.

The problem

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

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.

Approach overview

Problem Overview: You get a string s and a dictionary of valid words. The task is to determine if s can be split into a sequence of one or more dictionary words. Words can be reused, and segmentation must cover the entire string.

Approach 1: Dynamic Programming (O(n^2) time, O(n) space)

This approach treats the problem as a prefix segmentation check using dynamic programming. Create a boolean array dp where dp[i] means the substring s[0..i-1] can be formed using words from the dictionary. Convert the word list into a hash set for O(1) membership checks using a hash table. Iterate over every end index i, then scan earlier split points j. If dp[j] is true and s[j:i] exists in the dictionary, mark dp[i] as true. The key insight: if a valid segmentation exists up to position j, and the remaining substring is a dictionary word, the prefix ending at i is also valid. This bottom‑up method avoids recomputation and runs in O(n^2) time with O(n) space.

Approach 2: Memoization-based Depth First Search (O(n^2) time, O(n) space)

This strategy explores segmentations recursively using DFS combined with memoization. Start from index 0 and attempt every possible prefix that appears in the dictionary. When a valid prefix is found, recursively check the remaining suffix. Without caching, this produces exponential recursion because the same substring gets recomputed many times. Memoization fixes that by storing whether a starting index can eventually form a valid segmentation. Each index is evaluated once, and each check performs substring and dictionary lookups, resulting in roughly O(n^2) time. Space usage is O(n) for the recursion stack and memo table.

DFS with memoization is often easier to reason about because it mirrors the natural “try every word prefix” thought process. However, the bottom‑up DP version usually performs better in interviews because it avoids recursion overhead and makes the state transition explicit.

Recommended for interviews: The dynamic programming solution is the most commonly expected answer. It demonstrates strong understanding of prefix-based DP states and efficient substring validation with a hash set. Mentioning the recursive DFS first shows you understand the brute-force search space, then optimizing it with memoization or converting it to bottom-up DP shows problem-solving maturity.

Approach 1: Approach 1: Dynamic Programming

Dynamic Programming is a common approach for problems involving finding solutions over mutable subsets of an input set. We can use a boolean array 'dp' with length 'n+1', where 'n' is the length of the input string 's'. 'dp[i]' will indicate whether the substring 's[0...i-1]' can be segmented into words from the dictionary. We initialize 'dp[0]' to true since an empty substring can always be segmented.

For each position 'i' from 1 to n, iterate through each previous position 'j' from 0 to i-1, and check if the substring 's[j:i]' is in the word dictionary and if 'dp[j]' is true. If both conditions are met, set 'dp[i]' to true and break out of the loop.

The final answer will be found in 'dp[n]'.

Python

def wordBreak(s: str, wordDict: List[str]) -> bool:
    word_set = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[len(s)]

Java

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = 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] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

C++

#include <vector>
#include <string>
#include <unordered_set>

using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;

    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

JavaScript

var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const dp = Array(s.length + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length];
};

#include <stdbool.h>
#include <string.h>

bool wordBreak(char * s, char ** wordDict, int wordDictSize) {
    int n = strlen(s);
    bool dp[n + 1];
    memset(dp, false, sizeof(dp));
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && validSubstring(s + j, i - j, wordDict, wordDictSize)) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

bool validSubstring(char* start, int len, char ** wordDict, int wordDictSize) {
    for (int k = 0; k < wordDictSize; k++) {
        if (strncmp(start, wordDict[k], len) == 0 && strlen(wordDict[k]) == len) {
            return true;
        }
    }
    return false;
}

using System;
using System.Collections.Generic;

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        HashSet<string> dict = new HashSet<string>(wordDict);
        bool[] dp = new bool[s.Length + 1];
        dp[0] = true;

        for (int i = 1; i <= s.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.Length];
    }
}

The Python solution uses a dynamic programming array 'dp'. It iterates over usable substrings and checks their validity against the word set. The dp array is updated correspondingly.

Complexity

Time Complexity: O(n^2), following substring checks inside the loop.
Space Complexity: O(n), for the dp array.

Try this approach in the editor

Approach 2: Approach 2: Memoization-based Depth First Search

This approach utilizes Depth First Search (DFS) with the help of memoization to avoid redundant work. By storing the results of overlaps in a memoization structure, we cut down unnecessary recalculations. The recursive function attempts to segment the string from an index 'start' and uses a hash set for quick lookups of dictionary words. The function operates recursively trying to partition the string and caches results for indices already computed, preventing repetitions of partial solutions.

Python

def wordBreak(s: str, wordDict: List[str]) -> bool:
    memo = {}
    def wordBreakUtil(start):
        if start == len(s):
            return True
        if start in memo:
            return memo[start]

        for end in range(start + 1, len(s) + 1):
            if s[start:end] in wordDict and wordBreakUtil(end):
                memo[start] = True
                return True
        memo[start] = False
        return False

    return wordBreakUtil(0)

Java

import java.util.*;

public class Solution {
    private Map<Integer, Boolean> memo = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, new HashSet<>(wordDict), 0);
    }

    private boolean dfs(String s, Set<String> wordDict, int start) {
        if (start == s.length()) return true;
        if (memo.containsKey(start)) return memo.get(start);

        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end)) {
                memo.put(start, true);
                return true;
            }
        }
        memo.put(start, false);
        return false;
    }
}

C++

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool wordBreakUtil(string& s, unordered_set<string>& wordDict, int start, unordered_map<int, bool>& memo) {
        if (start == s.size()) return true;
        if (memo.find(start) != memo.end()) return memo[start];

        for (int end = start + 1; end <= s.size(); ++end) {
            if (wordDict.count(s.substr(start, end - start)) && wordBreakUtil(s, wordDict, end, memo)) {
                return memo[start] = true;
            }
        }

        return memo[start] = false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        unordered_map<int, bool> memo;
        return wordBreakUtil(s, dict, 0, memo);
    }
};

JavaScript

var wordBreak = function(s, wordDict) {
    const memo = new Map();

    const dfs = function(start) {
        if (start === s.length) return true;
        if (memo.has(start)) return memo.get(start);

        for (let end = start + 1; end <= s.length; end++) {
            if (wordDict.includes(s.substring(start, end)) && dfs(end)) {
                memo.set(start, true);
                return true;
            }
        }

        memo.set(start, false);
        return false;
    };

    return dfs(0);
};

#include <stdbool.h>
#include <string.h>

bool wordBreakUtil(char* s, int start, char** wordDict, int wordDictSize, int* memo) {
    if (start == strlen(s)) return true;
    if (memo[start] != -1) return memo[start];

    for (int end = start + 1; end <= strlen(s); end++) {
        if (isInDict(s + start, end - start, wordDict, wordDictSize) && wordBreakUtil(s, end, wordDict, wordDictSize, memo)) {
            return memo[start] = true;
        }
    }

    return memo[start] = false;
}

bool isInDict(char* start, int len, char** wordDict, int wordDictSize) {
    for (int i = 0; i < wordDictSize; i++) {
        if (strncmp(start, wordDict[i], len) == 0 && strlen(wordDict[i]) == len) {
            return true;
        }
    }
    return false;
}

 bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int n = strlen(s);
    int memo[n];
    memset(memo, -1, sizeof(memo));
    return wordBreakUtil(s, 0, wordDict, wordDictSize, memo);
}

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<int, bool> memo = new Dictionary<int, bool>();

    public bool WordBreak(string s, IList<string> wordDict) {
        HashSet<string> wordSet = new HashSet<string>(wordDict);
        return Dfs(s, wordSet, 0);
    }

    private bool Dfs(string s, HashSet<string> wordDict, int start) {
        if (start == s.Length) return true;
        if (memo.ContainsKey(start)) return memo[start];

        for (int end = start + 1; end <= s.Length; end++) {
            if (wordDict.Contains(s.Substring(start, end - start)) && Dfs(s, wordDict, end)) {
                memo[start] = true;
                return true;
            }
        }
        memo[start] = false;
        return false;
    }
}

The Python implementation leverages a recursive function 'wordBreakUtil' which employs memoization to store the outcomes of previously computed indices, reducing repeated work.

Complexity

Time Complexity: O(n^2) due to recursive calls over substring segments.
Space Complexity: O(n) maintained by the memo dictionary size.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function wordBreak(s: string, wordDict: string[]): boolean {
    const words = new Set(wordDict);
    const n = s.length;
    const f: boolean[] = new Array(n + 1).fill(false);
    f[0] = true;
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (f[j] && words.has(s.substring(j, i))) {
                f[i] = true;
                break;
            }
        }
    }
    return f[n];
}

func wordBreak(s string, wordDict []string) bool {
	words := map[string]bool{}
	for _, w := range wordDict {
		words[w] = true
	}
	n := len(s)
	f := make([]bool, n+1)
	f[0] = true
	for i := 1; i <= n; i++ {
		for j := 0; j < i; j++ {
			if f[j] && words[s[j:i]] {
				f[i] = true
				break
			}
		}
	}
	return f[n]
}

Rust

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let words: std::collections::HashSet<String> = word_dict.into_iter().collect();
        let mut f = vec![false; s.len() + 1];
        f[0] = true;
        for i in 1..=s.len() {
            for j in 0..i {
                f[i] |= f[j] && words.contains(&s[j..i]);
            }
        }
        f[s.len()]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Dynamic Programming	Time Complexity: O(n^2), following substring checks inside the loop. Space Complexity: O(n), for the dp array.
Approach 2: Memoization-based Depth First Search	Time Complexity: O(n^2) due to recursive calls over substring segments. Space Complexity: O(n) maintained by the memo dictionary size.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming (Bottom-Up)	O(n^2)	O(n)	Best general solution for interviews; avoids recursion and clearly models prefix segmentation.
DFS with Memoization	O(n^2)	O(n)	Useful when thinking recursively about prefixes; easier to derive from brute-force search.

Frequently asked questions

Is Word Break easy or hard?

Word Break is considered a medium difficulty problem. The challenge is recognizing that brute-force recursion leads to exponential complexity and converting that idea into dynamic programming or memoization.

How to solve Word Break in O(n)?

A strict O(n) solution is generally not achievable because every position may need to check multiple earlier split points. The practical optimal solution is O(n^2) using dynamic programming or DFS with memoization and a hash set for dictionary lookups.

What is the best approach for Word Break?

The dynamic programming approach is the most common solution. Use a boolean DP array where dp[i] represents whether the prefix ending at index i can be segmented using dictionary words. With a hash set for fast lookups, the algorithm runs in O(n^2) time and O(n) space.

What data structure is used in Word Break?

The solution typically uses a hash set to store dictionary words for O(1) membership checks and a dynamic programming array to track valid segmentations. Some optimized implementations also use a Trie to speed up prefix matching.

What is the time complexity of Word Break?

Both the optimized dynamic programming and memoized DFS solutions typically run in O(n^2) time, where n is the string length. Each position checks earlier split points and performs constant-time dictionary lookups using a hash set. Space complexity is O(n) for the DP array or memo cache.

Word Break Python or Java solution approach?

Python and Java implementations usually follow the same dynamic programming pattern: convert the dictionary to a set, iterate through string indices, and check valid split points. Both achieve O(n^2) time and O(n) space complexity.

Is Word Break asked at Google or Amazon interviews?

Word Break is a classic dynamic programming interview problem and appears frequently in coding interviews at companies like Amazon, Google, and Meta. Variants include returning all valid sentences (Word Break II) or optimizing with a Trie.

Word Break solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming

Approach 2: Approach 2: Memoization-based Depth First Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Word Break solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Dynamic Programming

Approach 2: Approach 2: Memoization-based Depth First Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems