Word Break II

XXX. Word Break II with Trie Optimization

Trie

Dynamic Programming

Backtracking

Problem Statement:

Given a string s and a list of dictionary words wordDict, return all possible sentences where the words are concatenated to form s. Each word in wordDict can be used multiple times, and the order of words in the result should match their order in s.

Algorithm:

1. Build a Trie to efficiently store and search the dictionary words.
2. Use a dynamic programming (DP) approach with a map to store valid sentences starting from each index in s.
3. Iterate from the end of s to the beginning to build sentences for each substring:
   • For each index, use the Trie to find valid words starting at that index.
   • For each valid word:
     • If it’s the last word in the string, add it as a sentence.
     • Otherwise, append it to all sentences formed from the remaining substring.
4. Return the list of sentences stored for the starting index 0.

Complexity:

Time: O(n × m), where n is the length of s and m is the total number of characters in wordDict | Space: O(n + m) for the DP map and Trie storage.

Java Implementation:

class TrieNode {
    boolean isEnd; // Indicates the end of a word
    TrieNode[] children; // Children nodes for each character (a-z)

    TrieNode() {
        isEnd = false;
        children = new TrieNode[26];
    }
}

class Trie {
    TrieNode root;

    Trie() {
        root = new TrieNode(); // Initialize the root of the Trie
    }

    // Insert a word into the Trie
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // Map character to Trie index
            if (node.children[index] == null)
                node.children[index] = new TrieNode(); // Create a new node if necessary
            node = node.children[index]; // Move to the next node
        }
        node.isEnd = true; // Mark the end of the word
    }
}

class Solution {
    public List wordBreak(String s, List wordDict) {
        // Build the Trie for the word dictionary
        Trie trie = new Trie();
        for (String word : wordDict)
            trie.insert(word);

        // Map to store results of subproblems
        Map> dp = new HashMap<>();

        // Iterate backward through the string to process substrings
        for (int startIdx = s.length(); startIdx >= 0; startIdx--) {
            List validSentences = new ArrayList<>();
            TrieNode currentNode = trie.root; // Start from the root of the Trie

            // Check all possible substrings starting at startIdx
            for (int endIdx = startIdx; endIdx < s.length(); endIdx++) {
                char c = s.charAt(endIdx);
                int index = c - 'a'; // Map character to Trie index
                if (currentNode.children[index] == null) break; // Stop if no valid path in Trie
                currentNode = currentNode.children[index]; // Move to the next node

                // If a valid word is found in the Trie
                if (currentNode.isEnd) {
                    String currentWord = s.substring(startIdx, endIdx + 1);
                    if (endIdx == s.length() - 1) {
                        // If this is the last word, add it as a valid sentence
                        validSentences.add(currentWord);
                    } else {
                        // Append to sentences formed from the remaining substring
                        List sentencesFromNextIndex = dp.get(endIdx + 1);
                        if (sentencesFromNextIndex != null) {
                            for (String sentence : sentencesFromNextIndex)
                                validSentences.add(currentWord + " " + sentence);
                        }
                    }
                }
            }
            // Store the results for the current startIdx
            dp.put(startIdx, validSentences);
        }

        // Return sentences formed from the entire string
        return dp.getOrDefault(0, new ArrayList<>());
    }
}