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

本文主要是介绍稀碎从零算法笔记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];}
};