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

class Trie {
private:
    TrieNode* root = new TrieNode;
public:
    void insert(string word) {
        TrieNode* curr = this->root;

        for (char c : word) {
            if (!curr->children.count(c)) {
                curr->children[c] = new TrieNode;
            }
            curr = curr->children[c];
        }
    }

    int search(string word) {
        TrieNode* curr = this->root;
        int len = 0;

        for (char c : word) {
            if (curr->children.size() != 1) {
                return len;
            }
            len += 1;
            curr = curr->children[c];
        }
        return len;
    }
};


class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        Trie trie;

        int len = INT_MAX;

        for (string word : strs) {
            trie.insert(word);
        }

        for (string word : strs) {
            len = min(len, trie.search(word));
        }

        return strs[0].substr(0, len);
    }
};
13200