Course4all

Word Break II

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Word Break II

Given a string s and a string dictionary wordDict, return all possible sentences that can be formed by adding spaces to s such that each word is a valid dictionary word.

Visual Representation

s = "catsanddog", dict = ["cat","cats","and","sand","dog"] Trie path 1: root -> c -> a -> t -> s (word) -> a -> n -> d (word) -> d -> o -> g (word) Trie path 2: root -> c -> a -> t (word) -> s -> a -> n -> d (word) -> d -> o -> g (word) Sentences: 1. "cats and dog" 2. "cat sand dog"
Hard

Examples

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Approach 1

Level I: Standard Recursion

Intuition

Iterate through the string s. If a prefix exists in the dictionary, recursively solve for the remaining suffix. O(2^N).
⏱ O(2^N)💾 O(N)
java
import java.util.*;
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, new HashMap<>());
    }
    private List<String> dfs(String s, List<String> wordDict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) return memo.get(s);
        List<String> res = new ArrayList<>();
        if (s.isEmpty()) {
            res.add("");
            return res;
        }
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> subList = dfs(s.substring(word.length()), wordDict, memo);
                for (String sub : subList) {
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }
        }
        memo.put(s, res);
        return res;
    }
}
Approach 2

Level III: Trie + DFS + Memoization

Intuition

Use a Trie to store words for fast prefix lookups. Combine DFS with memoization to store results for each starting index.
⏱ O(N * 2^N)💾 O(N * 2^N)
java
import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; String word = null; }
    public List<String> wordBreak(String s, List<String> wordDict) {
        Node root = new Node();
        for (String w : wordDict) { Node c = root; for (char x : w.toCharArray()) { int i = x-'a'; if (c.children[i] == null) c.children[i] = new Node(); c = c.children[i]; } c.word = w; }
        return dfs(s, 0, root, new HashMap<>());
    }
    private List<String> dfs(String s, int start, Node root, Map<Integer, List<String>> memo) {
        if (memo.containsKey(start)) return memo.get(start);
        List<String> res = new ArrayList<>();
        if (start == s.length()) { res.add(""); return res; }
        Node curr = root;
        for (int i = start; i < s.length(); i++) {
            int idx = s.charAt(i) - 'a'; if (curr.children[idx] == null) break;
            curr = curr.children[idx];
            if (curr.word != null) {
                List<String> sub = dfs(s, i + 1, root, memo);
                for (String w : sub) res.add(curr.word + (w.isEmpty() ? "" : " ") + w);
            }
        }
        memo.put(start, res); return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMaximum XOR with an Element from Array
Next Question →Boggle Game