<p>Write a function to find the longest common prefix string amongst an array of strings.</p>

<p>If there is no common prefix, return an empty string <code>&quot;&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;flower&quot;,&quot;flow&quot;,&quot;flight&quot;]
<strong>Output:</strong> &quot;fl&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> strs = [&quot;dog&quot;,&quot;racecar&quot;,&quot;car&quot;]
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There is no common prefix among the input strings.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strs.length &lt;= 200</code></li>
	<li><code>0 &lt;= strs[i].length &lt;= 200</code></li>
	<li><code>strs[i]</code> consists of only lowercase English letters.</li>
</ul>


    class TrieNode{
        public:
            unordered_map<char, TrieNode*> children;
            char val;
            bool isWord = false;

            TrieNode(){}
            TrieNode(char v){
                this->val = v;
            }
    };

    class Trie{
        private:
            TrieNode* root;
        public:
            Trie(){
                root = new TrieNode();
            }
            TrieNode* getTrieNode(){
                return root;
            }
            void insert(string word){
                TrieNode* temp = root;
                for (auto ch: word){
                    if (temp->children.find(ch) == temp->children.end()){
                        temp->children[ch] = new TrieNode(ch);
                    }
                    temp = temp->children[ch];
                }
                temp->isWord = true;
            }
    };
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        /*if (strs.empty())
            return "";
        string prefix = strs[0];
        for (string s: strs)
            while (s.find(prefix) != 0)     
                prefix = prefix.substr(0, prefix.length() - 1);
        return prefix;
    }*/

    Trie* pTrie = new Trie();
    for(auto str: strs){
        pTrie->insert(str);
    }

    string lcp("");
    TrieNode* curr = pTrie->getTrieNode();

    while (curr && !curr->isWord && (curr->children.size() == 1)){
        auto it = curr->children.begin();
        lcp += it->first;
        curr = it->second;
    }
    return lcp;
    }

};


12800