> For the complete documentation index, see [llms.txt](https://anton-veselskyi.gitbook.io/codding-problems-solutions/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/easy/longest-word-in-dictionary.md).

# Longest Word in Dictionary

## [Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary)

Given a list of strings `words` representing an English Dictionary, find the longest word in `words` that can be built one character at a time by other words in `words`. If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

**Example 1:**<br>

```

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
```

**Example 2:**<br>

```

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
```

**Note:**&#x41;ll the strings in the input will only contain lowercase letters.The length of `words` will be in the range `[1, 1000]`.The length of `words[i]` will be in the range `[1, 30]`.

## Solutions

### 🧠 Cpp

```cpp
#define all(x) begin(x),end(x)

class Solution
{

    struct TrieNode
    {
        char value = ' ';
        bool is_wordend = false;
        vector<shared_ptr<TrieNode>> nodes;
    };

    shared_ptr<TrieNode> createTrie(const vector<string>& words)
    {
        auto root = make_shared<TrieNode>();

        //translate vector of strings into trie
        for(const auto &str : words)
        {
            //start inserting new word from trie root
            auto trie_pointer = root;
            for(auto ch_iter = begin(str); ch_iter < end(str); ++ch_iter)
            {
                const char ch = *ch_iter;
                const bool char_present_in_trie = std::any_of(all(trie_pointer->nodes),
                    [&trie_pointer, ch](auto node)
                    {
                      bool found = node->value == ch;
                      if (found)
                          trie_pointer = node;
                        return found;
                    });

                //insert new node
                if(!char_present_in_trie)
                {
                    auto node = make_shared<TrieNode>();
                    node->value = ch;
                    trie_pointer->nodes.push_back(node);
                    trie_pointer = node;
                }

                if(ch_iter == prev(end(str)))
                    trie_pointer->is_wordend = true;
            }
        }

        return root;
    }
public:

    vector<string> get_words_formed_by_words(const shared_ptr<TrieNode> root)
    {
        vector<string> res;

        for(auto &leaf : root->nodes)
        {
            if(leaf->is_wordend)
            {
                res.emplace_back(1, leaf->value);

                vector<string> subres = get_words_formed_by_words(leaf);
                if(!subres.empty())
                {
                    string last_letter = res.back();
                    for(auto &str : subres)
                    res.push_back(last_letter + str);
                }
            }
        }

        return res;
    }

    string longestWord(vector<string>& words)
    {
        //O(n)
        auto root = createTrie(words);

        //O(n)
        vector<string> wfbw = get_words_formed_by_words(root);

        //O(n)
        return *max_element(all(wfbw), 
                            [](auto a, auto b)
                            {
                                return a.size() == b.size() ?
                                       a > b :
                                       a.size() <  b.size();
                            });
    }
};
```