稀碎从零算法笔记Day9-LeetCode:最长公共前缀

题型：字符串

链接：14. 最长公共前缀 - 力扣（LeetCode）

来源：LeetCode

题目描述（红字为笔者添加）

编写一个函数来查找字符串数组中的最长公共前缀(前X个字母相同)。

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

题目样例

示例 1：

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

示例 2：

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

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

题目思路

初见想要暴力解：创一个字符串来存前缀，当二维数组中的所有字符串都有这个字母的时候，塞到字符串中。否则就break掉，然后返回该字符串

但看了题解后，发现暴力优化下，就是“纵向遍历”

思路就是从第一个字符串的首字母开始，用一个char存起来。然后看剩下的字符串的首字母是否等于这个char。等于就让j++(可以遍历下一列了!)

这样子遍历需要可能中间有的字符串读完了，为了防止越界，循环条件处要看一下当前的 i 和strs[i] 的长度，别让 i 比这个长度大(要不就越界了！)

C++代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //纵向扫描：一次遍历每个字符串的第一列

        // 如果为空，返回空
        if(strs.size()==0)
            return "";

        int count=strs.size();//strs中字符串的个数
        int len=strs[0].size();
        //j遍历行，i遍历列
        for(int i=0;i<len;i++)
        {
            char test=strs[0][i];
            for(int j=1;j<count;j++)
            {
                if(strs[j][i]!=test||i==strs[j].size())//后面的或条件，是指“有的字符串被遍历完了”
                {
                    return strs[0].substr(0,i);//返回第一个字符串从索引0到索引i的字符串
                }
            }
        }
        //这里表示，把整个strs[0]遍历完了
        return strs[0];
    }
};