<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 Node{
    public:
    Node* links[26];
    bool flag;
    int childs;

    Node(){
        for(int i =0; i<26; i++) links[i] = NULL;
        flag = false;
        childs = 0;
    }

    bool containsKey(char c){
        return links[c-'a'] != NULL;
    }

    Node* get(char c){
        return links[c-'a'];
    }
     void put(char ch, Node* node) {
        links[ch - 'a'] = node;
        childs++;
    }


    bool isEnd(){
        return flag;
    }

    void setEnd(){
        flag = true;
    }
    int childCount(){
        return childs;
    }

};

class Trie{
    public:
    Node* root;
    Trie(){
        root = new Node;
        
    }
    void insert(string word){
        Node* node = root;
        for(char c: word){
            if(!node->containsKey(c)){
              node->put(c, new Node);
            }
            node = node->get(c);
        }
        node->setEnd();
    }

};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        Trie trie;
        for(auto it: strs){
            trie.insert(it);
        }

string ans = "";
        Node* node = trie.root;
        while(node -> childCount() == 1 && !node->isEnd()){
            for(int i =0; i<26; i++){
                if(node->links[i] != NULL){
                    ans += (i+'a');
                    node = node->links[i];
                    break;
                }
            }
        }
        return ans;
    }
};
11900