Word Break

Master this topic with zero to advance depth.

Word Break

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.

Visual Representation

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

s[0:4] = "leet" (Found!)
s[4:8] = "code" (Found!)
Result: True

DP Strategy:
dp[i] is true if s[0...i] can be segmented.
dp[i] = true if EXISTS j < i such that dp[j] is true AND s[j...i] is in wordDict.

Medium

Examples

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

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Return true because "applepenapple" can be segmented as "apple pen apple".

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try every possible prefix of the string. If a prefix is in the dictionary, recursively check if the remaining suffix can also be segmented into dictionary words.

Thought Process

For a string s, iterate i from 1 to len(s).
If s[0:i] is in wordDict:
- Recursively call canBreak(s[i:]).
Base case: If the remaining string is empty, return true.

⏱ O(2^N)💾 O(N) for recursion stack

Detailed Dry Run

s = "abc", wordDict = ["a", "bc"]

prefix "a" in Dict? Yes. Recurse on "bc".
prefix "b" in Dict? No.
prefix "bc" in Dict? Yes. Recurse on "".
Base case "" -> True.

java

import java.util.*;

public class Main {
    public static boolean wordBreak(String s, List<String> wordDict) {
        if (s.isEmpty()) return true;
        for (int i = 1; i <= s.length(); i++) {
            if (wordDict.contains(s.substring(0, i)) && wordBreak(s.substring(i), wordDict)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code"))); // true
    }
}

Approach 2

Level II: Memoization (Top-Down DP)

Intuition

The brute-force recursion checks all prefixes and re-explores the same suffixes repeatedly. By caching results for each starting index, we eliminate redundant work.

Visual

s = "leetcode", dict = ["leet", "code"]
memo[0]=T -> "leet" matches -> memo[4]=?
memo[4]=T -> "code" matches -> memo[8]=T

⏱ O(N^2 * L)💾 O(N)

Detailed Dry Run

s="catsdog", dict=["cats","dog"]. memo[0]: "cats" -> memo[4]. memo[4]: "dog" -> memo[7]=T. Cached!

java

import java.util.*;

public class Main {
    static Map<Integer, Boolean> memo = new HashMap<>();
    public static boolean solve(String s, Set<String> dict, int i) {
        if (i == s.length()) return true;
        if (memo.containsKey(i)) return memo.get(i);
        for (int j = i + 1; j <= s.length(); j++) {
            if (dict.contains(s.substring(i, j)) && solve(s, dict, j)) {
                memo.put(i, true);
                return true;
            }
        }
        memo.put(i, false);
        return false;
    }

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

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code"))); // true
    }
}

⚠️ Common Pitfalls & Tips

Use a Set for dictionary lookups (O(1)) instead of a list (O(L)). Without this, the overall complexity worsens significantly.

Approach 3

Level III: Dynamic Programming (Bottom-Up)

Intuition

We check every possible prefix of the string. If a prefix s[0...j] can be segmented (indicated by dp[j] = true), we then check if the remaining substring s[j...i] exists in the dictionary.

Thought Process

Initialize dp array of size n+1 with false.
dp[0] = true (empty string is always valid).
For i from 1 to n:
- For j from 0 to i-1:
  - If dp[j] is true AND s.substring(j, i) is in wordDict:
    - Set dp[i] = true and break.
Return dp[n].

⏱ O(N^2 * L) where L is max word length💾 O(N)

Detailed Dry Run

s = "leetcode", dict = ["leet", "code"]

i	j	Substring	dp[j]	Solution
0	-	-	T	Base Case
4	0	"leet"	T	dp[4] = True
8	4	"code"	T	dp[8] = True

java

import java.util.*;

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

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", Arrays.asList("leet", "code")));
    }
}

⚠️ Common Pitfalls & Tips

Be careful with substring indexing (inclusive start, exclusive end). Using a Set for dictionary lookup improves lookup time from O(W) to O(1) average.

← Previous QuestionLongest Common Subsequence

Next Question →Partition Equal Subset Sum

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.