Word Break II

Share

Given a string s and a dictionary of strings wordDict, return all possible sentences where s is segmented into dictionary words.

Example 1
Input: s="catsanddog", wordDict=["cat","cats","and","sand","dog"] → Output: ["cats and dog","cat sand dog"]
Example 2
Input: s="pineapplepenapple", wordDict=["apple","pen","applepen","pine","pineapple"] → Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Solution Approach

DFS with memoization. At each starting position, try all dictionary words as next segment. Cache results per position.

  • Build a Set from wordDict for O(1) lookup.
  • DFS(start): try all substrings s[start..end] that exist in dict.
  • Recursively get sentences for s[end..] and prepend current word.
  • Memoize results by start index.
Java
import java.util.*;

class Solution {
    Map<Integer,List<String>> memo = new HashMap<>();
    Set<String> dict;

    public List<String> wordBreak(String s, List<String> wordDict) {
        dict = new HashSet<>(wordDict);
        return dfs(s, 0);
    }
    private List<String> dfs(String s, int start) {
        if (memo.containsKey(start)) return memo.get(start);
        List<String> res = new ArrayList<>();
        if (start == s.length()) { res.add(""); return res; }
        for (int end = start+1; end <= s.length(); end++) {
            String word = s.substring(start, end);
            if (dict.contains(word)) {
                List<String> rest = dfs(s, end);
                for (String r : rest) res.add(word + (r.isEmpty() ? "" : " " + r));
            }
        }
        memo.put(start, res);
        return res;
    }
}
  • Time Complexity: O(N^3 + 2^N) in worst case
  • Space Complexity: O(N^2)