14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

 

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。  

---

每两个字符串合并

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans = "";
        if (strs.size() == 0){
            return ans;
        }
        ans = strs[0];
        for (int i = 1; i < strs.size(); i++){
            ans  = helper(ans, strs[i]);
            // cout << ans << endl;
            if (ans.size() == 0){
                break;
            }
        }
        return ans;
    }

    string helper(string str1, string str2) {
        int length = min(str1.size(), str2.size()), index = 0;
        string ans = "";
        while (index < length && str1[index] == str2[index]){
                index += 1;
        }
        // cout << "---" << index << endl;
        return str1.substr(0, index);
    }
};

纵向扫描

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        if (n == 0){
            return "";
        }
        int count = strs[0].size();
        for (int i = 0; i < count; i++){
            char ch = strs[0][i];
            for (int j = 1; j < n; j++){
                if (i == strs[j].size() || ch != strs[j][i]){
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};