<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:
        int val;
        unordered_map<int,TrieNode*> children;
        bool isTerminal;
    
        TrieNode(int val){
            this->val = val;
            this->isTerminal = false;
        }
};

void insert(TrieNode* root,string word) {
    int index = 0;
    TrieNode* ptr = root;

    while(index < word.length()){
        char ch = word[index];
        if((ptr->children).find(ch) != (ptr->children).end()){
            ptr = (ptr->children)[ch];
        }
        else{
            // not found;
            TrieNode* newNode = new TrieNode(ch);
            (ptr->children)[ch] = newNode;
            ptr = newNode;
        }
        index++;
    }
    ptr->isTerminal = true;
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        TrieNode* root = new TrieNode('-');

        // insert into trie
        for(int i=0;i<strs.size();i++){
            insert(root,strs[i]);
        }

        string ans = "";
        // main logic -> until root has single child -> push that char in ans
        TrieNode* ptr = root;
        while(ptr->isTerminal == false && (ptr->children).size() == 1){
            // push that single child in ans string
            // but how to access tat single char -> ???
            // better to use loop although we know it only runs once
            for(auto it : ptr->children){
                char ch = it.first;
                ans.push_back(ch);
                ptr = it.second;
            }
        }

        return ans;
    }
};
12800