Algorithm Day87 - Word Break

Posted on In , Views:

🧩 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.

You may assume the dictionary does not contain duplicate words.

💬 Examples

Example 1

1
2
3
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: "leetcode" -> "leet" + "code"

Example 2

1
2
3
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" -> "apple" + "pen" + "apple"

Example 3

1
2
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

💡 Intuition

We want to determine whether s can be split into valid words from wordDict. Two common approaches:

  1. Dynamic Programming (DP): Let dp[i] be true if s[0..i) can be segmented. For each i, check all possible previous cuts j < i and if dp[j] is true and s[j..i) is in wordDict, set dp[i] = true.

  2. BFS / Trie: Treat positions as nodes and edges when substring is a word; run BFS from position 0 to n to avoid redundant work.

DP is simple and efficient when implemented with a hash set for dictionary lookups and pruning via max word length.

🔢 Java Code (DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

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;
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
        
        for (int i = 1; i <= n; i++) {
            for (int l = 1; l <= maxLen && l <= i; l++) {
                if (!dp[i - l]) continue;
                if (dict.contains(s.substring(i - l, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

⏱ Complexity Analysis

  • Time: O(n * L) where n = length of s, L = max word length; substring/hash lookups average O(1).
  • Space: O(n) for DP array + O(m) for dictionary storage.

✍️ Summary

  • DP with dictionary lookup and max-word-length optimization is the standard solution.
  • BFS is an alternative that often performs well with proper visited pruning.

Related problems: lc-140 (Word Break II), lc-472 (Concatenated Words).