Longest Word With All Prefixes

class Solution {
    struct Node {
        Node* child[26]{};
        bool isEnd = false;
    };
public:
    string longestWord(vector<string>& words) {
        Node* root = new Node();
        for (auto& w : words) {
            Node* cur = root;
            for (char c : w) {
                int i = c - 'a';
                if (!cur->child[i]) cur->child[i] = new Node();
                cur = cur->child[i];
            }
            cur->isEnd = true;
        }
        string best, path;
        function<void(Node*)> dfs = [&](Node* node) {
            if ((int)path.size() > (int)best.size()) best = path;
            for (int i = 0; i < 26; ++i) {
                if (node->child[i] && node->child[i]->isEnd) {
                    path.push_back('a' + i);
                    dfs(node->child[i]);
                    path.pop_back();
                }
            }
        };
        dfs(root);
        return best;
    }
};

type trieNode struct {
    child [26]*trieNode
    isEnd bool
}

func longestWord(words []string) string {
    root := &trieNode{}
    for _, w := range words {
        cur := root
        for i := 0; i < len(w); i++ {
            idx := w[i] - 'a'
            if cur.child[idx] == nil {
                cur.child[idx] = &trieNode{}
            }
            cur = cur.child[idx]
        }
        cur.isEnd = true
    }
    var best, path []byte
    var dfs func(node *trieNode)
    dfs = func(node *trieNode) {
        if len(path) > len(best) {
            best = append(best[:0], path...)
        }
        for i := 0; i < 26; i++ {
            if node.child[i] != nil && node.child[i].isEnd {
                path = append(path, byte('a'+i))
                dfs(node.child[i])
                path = path[:len(path)-1]
            }
        }
    }
    dfs(root)
    return string(best)
}

from typing import List, Optional

class _TrieNode:
    __slots__ = ('child', 'is_end')

    def __init__(self) -> None:
        self.child: List[Optional['_TrieNode']] = [None] * 26
        self.is_end = False

class Solution:
    def longestWord(self, words: List[str]) -> str:
        root = _TrieNode()
        for w in words:
            cur = root
            for ch in w:
                i = ord(ch) - ord('a')
                if cur.child[i] is None:
                    cur.child[i] = _TrieNode()
                cur = cur.child[i]
            cur.is_end = True

        best: List[str] = []
        path: List[str] = []

        def dfs(node: _TrieNode) -> None:
            nonlocal best
            if len(path) > len(best):
                best = path.copy()
            for i in range(26):
                nxt = node.child[i]
                if nxt is not None and nxt.is_end:
                    path.append(chr(ord('a') + i))
                    dfs(nxt)
                    path.pop()

        dfs(root)
        return ''.join(best)

function longestWord(words) {
    const A = 'a'.charCodeAt(0);
    const root = { child: new Array(26).fill(null), isEnd: false };
    for (const w of words) {
        let cur = root;
        for (let i = 0; i < w.length; i++) {
            const idx = w.charCodeAt(i) - A;
            if (!cur.child[idx]) cur.child[idx] = { child: new Array(26).fill(null), isEnd: false };
            cur = cur.child[idx];
        }
        cur.isEnd = true;
    }
    let best = '';
    const path = [];
    const dfs = (node) => {
        if (path.length > best.length) best = path.join('');
        for (let i = 0; i < 26; i++) {
            if (node.child[i] && node.child[i].isEnd) {
                path.push(String.fromCharCode(A + i));
                dfs(node.child[i]);
                path.pop();
            }
        }
    };
    dfs(root);
    return best;
}

class TrieNode {
    TrieNode[] child = new TrieNode[26];
    boolean isEnd;
}

class Solution {
    private String best;
    private StringBuilder path;

    public String longestWord(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode cur = root;
            for (int i = 0; i < w.length(); i++) {
                int idx = w.charAt(i) - 'a';
                if (cur.child[idx] == null) cur.child[idx] = new TrieNode();
                cur = cur.child[idx];
            }
            cur.isEnd = true;
        }
        best = "";
        path = new StringBuilder();
        dfs(root);
        return best;
    }

    private void dfs(TrieNode node) {
        if (path.length() > best.length()) best = path.toString();
        for (int i = 0; i < 26; i++) {
            if (node.child[i] != null && node.child[i].isEnd) {
                path.append((char) ('a' + i));
                dfs(node.child[i]);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

interface TrieNode {
    child: (TrieNode | null)[];
    isEnd: boolean;
}

function longestWord(words: string[]): string {
    const A = 'a'.charCodeAt(0);
    const makeNode = (): TrieNode => ({ child: new Array(26).fill(null), isEnd: false });
    const root: TrieNode = makeNode();
    for (const w of words) {
        let cur = root;
        for (let i = 0; i < w.length; i++) {
            const idx = w.charCodeAt(i) - A;
            if (!cur.child[idx]) cur.child[idx] = makeNode();
            cur = cur.child[idx]!;
        }
        cur.isEnd = true;
    }
    let best = '';
    const path: string[] = [];
    const dfs = (node: TrieNode): void => {
        if (path.length > best.length) best = path.join('');
        for (let i = 0; i < 26; i++) {
            const nxt = node.child[i];
            if (nxt && nxt.isEnd) {
                path.push(String.fromCharCode(A + i));
                dfs(nxt);
                path.pop();
            }
        }
    };
    dfs(root);
    return best;
}