Solution

Method 1 – Trie and DFS

Intuition

To find the longest word where every prefix is also in the list, we use a Trie to store all words and then perform DFS, only continuing down paths where all prefixes are valid words. This ensures that the word we build has all its prefixes present.

Approach

Insert all words into a Trie, marking the end of each word.
Perform DFS from the root, only visiting nodes that mark the end of a word (valid prefix).
Track the word formed at each node. Update the answer if a longer or lexicographically smaller word is found.
Return the longest valid word found.

Code

[{"language":"C++","code":"class TrieNode {\npublic:\n    TrieNode* children[26] = {};\n    bool isWord = false;\n};\nclass Solution {\npublic:\n    string ans = \"\";\n    void dfs(TrieNode* node, string& path) {\n        if (path.size() > ans.size() || (path.size() == ans.size() && path < ans)) ans = path;\n        for (int i = 0; i < 26; ++i) {\n            if (node->children[i] && node->children[i]->isWord) {\n                path.push_back('a' + i);\n                dfs(node->children[i], path);\n                path.pop_back();\n            }\n        }\n    }\n    string longestWord(vector<string>& words) {\n        TrieNode* root = new TrieNode();\n        for (auto& w : words) {\n            TrieNode* node = root;\n            for (char c : w) {\n                if (!node->children[c-'a']) node->children[c-'a'] = new TrieNode();\n                node = node->children[c-'a'];\n            }\n            node->isWord = true;\n        }\n        string path = \"\";\n        dfs(root, path);\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"type TrieNode struct {\n    children [26]*TrieNode\n    isWord bool\n}\nfunc longestWord(words []string) string {\n    root := &TrieNode{}\n    for _, w := range words {\n        node := root\n        for _, c := range w {\n            idx := int(c - 'a')\n            if node.children[idx] == nil {\n                node.children[idx] = &TrieNode{}\n            }\n            node = node.children[idx]\n        }\n        node.isWord = true\n    }\n    var ans, path string\n    var dfs func(*TrieNode, string)\n    dfs = func(node *TrieNode, path string) {\n        if len(path) > len(ans) || (len(path) == len(ans) && path < ans) {\n            ans = path\n        }\n        for i := 0; i < 26; i++ {\n            if node.children[i] != nil && node.children[i].isWord {\n                dfs(node.children[i], path+string('a'+i))\n            }\n        }\n    }\n    dfs(root, \"\")\n    return ans\n}","lang":"go"},{"language":"Java","code":"class TrieNode {\n    TrieNode[] children = new TrieNode[26];\n    boolean isWord = false;\n}\nclass Solution {\n    String ans = \"\";\n    void dfs(TrieNode node, StringBuilder path) {\n        if (path.length() > ans.length() || (path.length() == ans.length() && path.toString().compareTo(ans) < 0)) ans = path.toString();\n        for (int i = 0; i < 26; i++) {\n            if (node.children[i] != null && node.children[i].isWord) {\n                path.append((char)('a'+i));\n                dfs(node.children[i], path);\n                path.deleteCharAt(path.length()-1);\n            }\n        }\n    }\n    public String longestWord(String[] words) {\n        TrieNode root = new TrieNode();\n        for (String w : words) {\n            TrieNode node = root;\n            for (char c : w.toCharArray()) {\n                if (node.children[c-'a'] == null) node.children[c-'a'] = new TrieNode();\n                node = n

Related Tags