LeetCode 14. 最长公共前缀
📌 题目描述
题目级别：简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
- 示例 1:
输入：strs = ["flower","flow","flight"]
输出："fl"
💡 破题思路：纵向扫描 (Vertical Scanning)
要找多个字符串的“公共前缀”，最符合人类直觉的方法就是纵向扫描。
我们把所有字符串上下对齐，然后从第 0 列开始，一列一列地往下看：
- 如果这一列的所有字符都一样，那这个字符就是公共前缀的一部分，把它收进结果里。
- 如果这一列出现了哪怕一个不一样的字符，或者某一个字符串已经提前见底了，说明公共前缀到此为止，立刻结束判定。
极客防越界细节：
为了防止在外层循环（列遍历）时，索引超过了某个较短字符串的长度而导致访问越界（Core Dump），我们在正式扫描前，先遍历一遍数组，找到所有字符串中的最短长度 mi。
这样外层循环最多只会执行 mi 次，从物理根源上彻底杜绝了越界崩溃的可能，代码运行极其稳健。
💻 C++ 代码实现 (原汁原味作者版)
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res = "";
int m = strs.size();
int l = 0;
// 1. 防御性编程：提前算出最短的字符串长度 mi
int mi = strs[0].size();
for (int i = 0; i < m; i ++ )
mi = min(mi, int(strs[i].size()));
int flag = 0; // 熔断标记
// 2. 外层循环：遍历每一列 (最多遍历到最短的那个字符串的末尾)
for (int i = 0; i < mi; i ++ )
{
// 3. 内层循环：纵向比较每一个字符串的第 i 个字符
for (int j = 0; j < m; j ++ )
{
// 以第 0 个字符串的字符为基准，只要发现有不相等的
if (strs[j][i] != strs[0][i])
{
flag = 1; // 触发熔断标记
break; // 跳出内层循环
}
}
// 如果触发了熔断，说明公共前缀断了，直接跳出外层循环
if (flag) break;
// 如果这一列全部通关，将其加入结果集
res += strs[0][i];
}
return res;
}
};
