Leetcode 720 Solution

This article provides solution to leetcode question 720 (longest-word-in-dictionary)

https://leetcode.com/problems/longest-word-in-dictionary

Solution

class TrieNode { public: char ch; vector<TrieNode*> children;
TrieNode(char _ch){ ch = _ch; children.resize(26); } };
class Solution { TrieNode root;
public: Solution(): root(0) { }
string longestWord(vector<string>& words) { int maxlen = 0; string ans; sort(words.begin(), words.end());
for (auto word: words) { TrieNode* curr = &root;
int i = 0; for (; i < word.size(); i++) { char ch = word[i];
if (!curr->children[ch - 'a']) { if (i == word.size() - 1) { auto node = new TrieNode(ch); curr->children[ch - 'a'] = node; } else break; } else curr = curr->children[ch - 'a']; }
if (maxlen < i && i == word.size()) { maxlen = i; ans = word; } }
return ans; } };