<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 Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1) {
            return strs[0];
        }
        // int min_size = 201;
        // for (const auto& s : strs) {
        //     min_size = std::min(min_size, s.size());
        // }
        const string min_size_str = *std::min_element(
            strs.begin(), strs.end(), [](const string s1, const string s2) -> bool { return s1.size() < s2.size(); }
        );
        if (min_size_str == "") {
            return "";
        }
        vector<string> prefixes(min_size_str.size() + 1, "");
        string curr_str = "";
        for (int i = 0; i < min_size_str.size(); ++i) {
            curr_str += min_size_str[i];
            prefixes[i + 1] = curr_str;
        }

        int prefix_id = prefixes.size() - 1;
        for (int i = 0; i < strs.size(); ++i) {
            while (!strs[i].starts_with(prefixes[prefix_id])) {
                --prefix_id;
                if (prefix_id <= 0) {
                    return "";
                }
            }
        }
        return prefixes[prefix_id];
    }
};
12200