Word Break II

class TrieNode {
public:
    bool isWord;
    TrieNode* childNodes[26];
    
    TrieNode() {
        isWord = false;
        for (int i = 0; i < 26; i++) {
            childNodes[i] = nullptr;
        }
    }
};
    
class WordTrie {
public:
    TrieNode* start;
    
    WordTrie() { start = new TrieNode(); }
    
    void append(string term) {
        TrieNode* current = start;
        for (char ch : term) {
            int pos = ch - 'a';
            if (!current->childNodes[pos]) {
                current->childNodes[pos] = new TrieNode();
            }
            current = current->childNodes[pos];
        }
        current->isWord = true;
    }
};
    
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& dictionary) {
        // Create and populate the Trie from given dictionary
        WordTrie wordTrie;
        for (string word : dictionary) {
            wordTrie.append(word);
        }
    
        // Dictionary to hold the solutions for subproblems
        unordered_map<int, vector<string>> memo;
    
        // Process the input string from end to start
        for (int start = s.size(); start >= 0; start--) {
            // This will collect all viable sentence formations from this point
            vector<string> sentences;
    
            // Starting node is root of Trie
            TrieNode* trackerNode = wordTrie.start;
    
            // Process each substring starting from 'start'
            for (int end = start; end < s.size(); end++) {
                char ch = s[end];
                int idx = ch - 'a';
    
                // If no node for this character, break out of current loop
                if (!trackerNode->childNodes[idx]) {
                    break;
                }
    
                // Move to the next node corresponding to the character
                trackerNode = trackerNode->childNodes[idx];
    
                // If node marks completion of a word in the Trie
                if (trackerNode->isWord) {
                    string foundWord = s.substr(start, end - start + 1);
    
                    // Directly add word as a sentence if it reaches the string's end
                    if (end == s.size() - 1) {
                        sentences.push_back(foundWord);
                    } else {
                        // Combine this word with results from memoization of the next index
                        for (string subsequent : memo[end + 1]) {
                            sentences.push_back(foundWord + " " + subsequent);
                        }
                    }
                }
            }
    
            // Save results in the memo
            memo[start] = sentences;
        }
    
        // Return all combinations starting from index 0
        return memo[0];
    }
};

class PrefixTreeNode {
    
    boolean terminal;
    PrefixTreeNode[] edges;
    
    PrefixTreeNode() {
        terminal = false;
        edges = new PrefixTreeNode[26];
    }
}
    
class PrefixTree {
    
    PrefixTreeNode entryPoint;
    
    PrefixTree() {
        entryPoint = new PrefixTreeNode();
    }
    
    void addWord(String word) {
        PrefixTreeNode node = entryPoint;
        for (char charElement : word.toCharArray()) {
            int idx = charElement - 'a';
            if (node.edges[idx] == null) {
                node.edges[idx] = new PrefixTreeNode();
            }
            node = node.edges[idx];
        }
        node.terminal = true;
    }
}
    
class Solution {
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        PrefixTree prefixTree = new PrefixTree();
        for (String word : wordDict) {
            prefixTree.addWord(word);
        }
    
        Map<Integer, List<String>> memo = new HashMap<>();
    
        for (int start = s.length(); start >= 0; start--) {
            List<String> results = new ArrayList<>();
    
            PrefixTreeNode current = prefixTree.entryPoint;
    
            for (int end = start; end < s.length(); end++) {
                char ch = s.charAt(end);
                int idx = ch - 'a';
    
                if (current.edges[idx] == null) {
                    break;
                }
    
                current = current.edges[idx];
    
                if (current.terminal) {
                    String snip = s.substring(start, end + 1);
    
                    if (end == s.length() - 1) {
                        results.add(snip);
                    } else {
                        List<String> nextParts = memo.get(end + 1);
                        for (String part : nextParts) {
                            results.add(snip + " " + part);
                        }
                    }
                }
            }
    
            memo.put(start, results);
        }
    
        return memo.getOrDefault(0, new ArrayList<>());
    }
}

class TrieNode:
    def __init__(self):
        self.endOfWord = False
        self.branches = [None] * 26  # Alphabet node storage
    
    
class WordTrie:
    def __init__(self):
        self.rootNode = TrieNode()
    
    def addWord(self, word):
        node = self.rootNode
        for letter in word:
            pos = ord(letter) - ord("a")
            if not node.branches[pos]:
                node.branches[pos] = TrieNode()
            node = node.branches[pos]
        node.endOfWord = True
    
    
class WordBreakSolver:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        trie = WordTrie()
        for word in wordDict:
            trie.addWord(word)
    
        memo = {}
    
        for i in range(len(s), -1, -1):
            valid_phrases = []
    
            node = trie.rootNode
    
            for j in range(i, len(s)):
                char = s[j]
                idx = ord(char) - ord("a")
    
                if not node.branches[idx]:
                    break
    
                node = node.branches[idx]
    
                if node.endOfWord:
                    found_word = s[i : j + 1]
                        
                    if j == len(s) - 1:
                        valid_phrases.append(found_word)
                    else:
                        next_words = memo.get(j + 1, [])
                        for seq in next_words:
                            valid_phrases.append(found_word + " " + seq)
    
            memo[i] = valid_phrases
    
        return memo.get(0, [])