StringProblem 17 of 43

Word break Problem [Very Imp]

Brute Force
Time: O(2ⁿ × n)
Space: O(n)
Optimal
Time: O(n² × m)
Space: O(n)

Problem Statement

Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example:

  • Input: s = "leetcode", wordDict = ["leet", "code"]

  • Output: true

  • Explanation: "leetcode" = "leet" + "code"

  • Input: s = "applepenapple", wordDict = ["apple", "pen"]

  • Output: true

  • Explanation: "applepenapple" = "apple" + "pen" + "apple"

  • Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

  • Output: false

Approach 1: Brute Force (Recursion)

Intuition

Try every possible prefix. If it's in the dictionary, recursively check if the remaining suffix can be segmented.

Algorithm

  1. If string is empty, return true
  2. Try all prefixes of the string
  3. If prefix is in dictionary and suffix can be segmented, return true
  4. Return false if no valid segmentation found
java
import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        return canBreak(s, dict);
    }
    
    private boolean canBreak(String s, Set<String> dict) {
        if (s.isEmpty()) {
            return true;
        }
        
        for (int i = 1; i <= s.length(); i++) {
            String prefix = s.substring(0, i);
            String suffix = s.substring(i);
            
            if (dict.contains(prefix) && canBreak(suffix, dict)) {
                return true;
            }
        }
        
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - In worst case, trying all possible segmentations
  • Space Complexity: O(n) - Recursion stack

Approach 2: Memoization (Top-Down DP)

Intuition

Many subproblems are computed multiple times. Cache results for substrings we've already processed.

java
import java.util.*;

public class Solution {
    private Map<Integer, Boolean> memo = new HashMap<>();
    
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        memo.clear();
        return canBreak(s, 0, dict);
    }
    
    private boolean canBreak(String s, int start, Set<String> dict) {
        if (start == s.length()) {
            return true;
        }
        
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        
        for (int end = start + 1; end <= s.length(); end++) {
            String prefix = s.substring(start, end);
            if (dict.contains(prefix) && canBreak(s, end, dict)) {
                memo.put(start, true);
                return true;
            }
        }
        
        memo.put(start, false);
        return false;
    }
}

Complexity Analysis

  • Time Complexity: O(n² × m) where m is max word length
  • Space Complexity: O(n) - Memoization table

Approach 3: Tabulation (Bottom-Up DP)

Intuition

dp[i] represents whether s[0..i-1] can be segmented. Build the solution bottom-up.

Algorithm

  1. dp[0] = true (empty string can be segmented)
  2. For each position i, check all positions j < i
  3. If dp[j] is true and s[j..i-1] is in dictionary, then dp[i] = true
java
import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        
        // dp[i] = true if s[0..i-1] can be segmented
        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];
    }
    
    // Optimized
    public boolean wordBreakOptimized(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

Complexity Analysis

  • Time Complexity: O(n² × m) where m is average word length for substring operations
  • Space Complexity: O(n) - DP array

Approach 4: Word Break II (Get All Segmentations)

Intuition

Return all possible segmentations instead of just checking if possible.

Using Trie for Dictionary

Intuition

For large dictionaries, use a Trie for efficient prefix matching.

Key Takeaways

  1. Dynamic Programming is the key - overlapping subproblems
  2. Bottom-up DP is often cleaner than memoization
  3. Optimization: Limit inner loop to max word length
  4. Trie is useful for large dictionaries
  5. Word Break II returns all segmentations - more complex
  6. This is a classic DP problem (LeetCode 139, 140)
  7. Similar to the coin change problem structure
  8. Time complexity can be improved with Trie to O(n × m) where m is max word length
Previous
Balanced Parenthesis problem [Imp]
Next
Rabin Karp Algo