<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 trie
{
    public:
    bool isLeaf;
    struct trie* child[26];
    trie()
    {
        isLeaf = false;
        for (int i = 0; i <26; i++)
        {
            child[i] = NULL;
        }
    }

    void insert(string input)
    {
        trie* cur = this;
        for (int i = 0; i <input.length(); i++)
        {
            int index = input[i] - 'a';
            if (cur->child[index] == NULL)
            {
                cur->child[index] = new trie();
            }

            cur = cur->child[index];
        }

        cur->isLeaf = true;
    }

    bool isOneChild()
    {
        int count = 0;
        trie* cur = this;

        for (int i = 0; i < 26; i++)
        {
            if (cur->child[i] != NULL)
            {
                count++;
            }
            
        }

        return count == 1 ? true : false;
    }
    string lcs(string input)
    {
        string res;
        trie* cur = this;

        for (int i = 0; i <input.length(); i++)
        {
            if (cur->isOneChild())
            {
                res.push_back(input[i]);
                cur = cur->child[input[i] - 'a'];
            }
            else
            {
                break;
            }

            if (cur->isLeaf)
            {
                break;
            }
        }

        return res;

    }
};


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

        trie* root = new trie();


        for (int i = 0; i < strs.size(); i++)
        {
            string temp = strs[i];
            if (temp == "")
            {
                return temp;
            }
            root->insert(temp);
        }

        return root->lcs(strs[0]);
        
    }
};

11900