2707. Extra Characters in a String

T: O(M*K + n^2*K)
S: O(M*K + n)

class Solution {
    private TrieNode root;
    
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }

    class Trie {
        Trie() {
            root = new TrieNode();
        }

        public void insert(String s) {
            TrieNode node = root;
            for (char c : s.toCharArray()) {
                if (node.children[c - 'a'] == null) { 
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    }

    public int minExtraChar(String s, String[] dictionary) {
        Trie trie = new Trie();
        for (String d : dictionary) { // O(MK)
            trie.insert(d);
        }
        Integer[] memo = new Integer[s.length()];
        return dfs(s, trie, 0, memo);
    }
    private int dfs(String s, Trie trie, int i, Integer[] memo) {
        if (i == s.length()) {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        TrieNode node = root;
        int result = 1 + dfs(s, trie, i+1, memo); // skip one char and run others (for each position posibility)
        for (int j = i ; j < s.length(); j++) { // O(n^2, dfs & for)
            char c = s.charAt(j);
            if (node.children[c - 'a'] == null) {
                break;
            }
            node = node.children[c - 'a'];
            if (node.isWord) { // if find this word [i to j] in Trie
                result = Math.min(result, dfs(s, trie, j+1, memo)); // so run j+1 part
            }

        }
        return memo[i] = result;
    }
}
/**
T: O(M*K + n^2*K)
S: O(M*K + n)
 */
            // if (set.contains(s.substring(i, j+1))) { // this [i to j] part in dictionary
            //     result = Math.min(result, dfs(s, trie, j+1, memo)); // so run j+1 part
            // }