14. 最长公共前缀

简介

在看Leetcode中专项突破的数组和字符串专题中，看完字符串章节后，进行题目练习，看到 14. 最长公共前缀 一道简单的题目，但是反复调试了许久，才找到bug所在。

题目

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

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

case 1 :

输入：strs = ["flower","flow","flight"]
输出："fl"

case 2 :

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

思考过程

最长公共前缀需要挨个遍历字符串，而且需要更新公共的前缀字符串已下一个进行比较，基本就是循环。但是实现代码的过程中考虑的情况有点少，没有想到好的办法更新前缀字符串，导致run fail, 看来题解之后，恍然大雾。

#include<iostream>
#include<vector>

using namespace std;

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

    string longestCommonPrefix(const string & str1, const string str2){
        // tips 使用系统函数
        int length = min(str1.size(), str2.size());
        int index = 0;
        while( index < length && str1[index] == str2[index]){
            index++;
        }
        // tips 使用string.sunstr fu
        return str1.substr(0,index);
    }
};

int main(){
    vector<string> strs = {"flower","flow","flight"};
    Solution test_class;
    string str = test_class.longestCommonPrefix(strs);
    cout << "strs prefix : " << str << endl
}

上面的解决过程是横向遍历，看了题解之后，纵向遍历的解决方法更加方便，也容易更加理解