14. 最长公共前缀题解：多方法详解与C++实现
问题描述
给定字符串数组，找出所有字符串的最长公共前缀。若不存在则返回空字符串。
示例：
输入：["flower","flow","flight"]
输出："fl"
方法一：纵向扫描（逐字符比较）
算法思想
逐个字符比较所有字符串的同一列，直到出现不匹配字符为止。
复杂度分析
- 时间复杂度：O(m*n)
(m=最短字符串长度，n=字符串数量) - 空间复杂度：O(1)
C++实现
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.empty()) return "";int min_len = INT_MAX;for(auto& s : strs) min_len = min(min_len, (int)s.size());for(int j=0; j<min_len; ++j) {char c = strs[0][j];for(int i=1; i<strs.size(); ++i) {if(strs[i][j] != c)return strs[0].substr(0,j);}}return strs[0].substr(0,min_len);}
};
方法二：横向扫描（迭代比较）
算法流程
- 取第一个字符串为初始前缀
- 依次与后续字符串比较，逐步缩短前缀
代码实现
string longestCommonPrefix(vector<string>& strs) {if(strs.empty()) return "";string prefix = strs[0];for(int i=1; i<strs.size(); ++i){while(strs[i].find(prefix) != 0){prefix = prefix.substr(0, prefix.length()-1);if(prefix.empty()) return "";}}return prefix;
}
