Leetcode 720 Solution

This article provides solution to leetcode question 720 (longest-word-in-dictionary)
Categories:
Tags:
Access this page by simply typing in "lcs 720" in your browser address bar if you have bunnylol configured.

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;
    }
};