Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.

最长公共前缀

看到前缀 我就想到了tries 树， 但是一看这题是easy........
我们假设 有 N个字符串 ， 平均长度为 M
我们暴力比较 第 i (0..m) 位， 复杂度为 N*M
其实用 tries树 时间复杂度反而高，而且还要开空间。。。
所以这题就暴力比较啦。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
        if(strs.empty())
            return "";
        
        // 特殊处理 strs 只有一个字符串 的情况 
        if(strs.size()==1){
            return strs[0];
        }
        
        int ptr = 0;
        // 循环比较 每个字符串的 第 i 位 
        
        while(true){
            
            // 循环 比较！ 如果出现 1. 前后不一致  或者  2. 某一字符串越界 
            // 这个循环 不能处理 strs.size() <=1 的情况 所以上面要特殊处理
            for(int i =1; i <strs.size();++i){
                if( ptr == strs[i].size() || strs[i][ptr] != strs[i-1][ptr]){
                    //结束循环 打印结果
                    return strs[0].substr(0,ptr);
                }
            }
            ptr++;
        }
 
    }
};

image.png