题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
思路
-
边界条件：如果字符串数组为空，直接返回空字符串。如果数组中只有一个字符串，则返回该字符串。
-
逐个比较字符：
- 从第一个字符串开始，逐个字符与后续字符串进行比较。
- 当遇到不相同的字符时，停止比较，并返回到当前字符为止的公共前缀。
-
返回结果：如果没有找到公共前缀，返回空字符串。
代码实现
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.empty())return "";if(strs.size()==1)return strs[0];//首先检查字符串数组是否为空，或者是否只有一个字符串。string prefix=strs[0];//将第一个字符串设置为初始公共前缀。for(int i=1;i<strs.size();i++){while(strs[i].find(prefix)!=0){//使用 find 方法检查当前字符串是否以公共前缀开头。prefix=prefix.substr(0,prefix.size()-1);//如果不是，则不断缩短前缀，直到找到一个匹配的前缀。if(prefix.empty())return "";}}return prefix;}
};复杂度分析
-
时间复杂度：O(n * m)，其中 n 是字符串数组的长度，m 是最短字符串的长度。最坏情况下，我们需要对每个字符串的所有字符进行比较。
-
空间复杂度：O(1)，只使用了常量空间来存储前缀变量。
