LeetCode 14 最长公共前缀

1. 题目14. 最长公共前缀题目描述编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。示例输入strs [flower,flow,flight]输出fl输入strs [dog,racecar,car]输出约束(1 strs.length 200)(0 strs[i].length 200)strs[i]仅由小写英文字母组成2. 最佳解题思路描述纵向扫描直观易懂最长公共前缀长度不可能超过数组中最短字符串长度先求出最短串长度minLen按列遍历每一列代表同一个前缀下标 i取出第 i 列所有字符串的字符两两对比若全部相等公共前缀长度 1出现不等字符直接终止循环截取第一个字符串前num个字符作为答案返回。优势逻辑贴合题意容易手写实现时间 (O(mn))m 最短串长度n 字符串数量空间 (O(1))。3. 我的可优化代码逻辑正确可 AC存在多处不规范、冗余点class Solution { public: string longestCommonPrefix(vectorstring strs) { int num 0; int min 10000; for(int i0;istrs.size();i){ if(strs[i].size()min){ min strs[i].size(); } } for(int i0;imin;i){ int f1; for(int j0;jstrs.size()-1;j){ if(strs[j][i]!strs[j1][i]){ f0; break; } } if(f1){ num; } if(f0){ break; } } string s; for(int i0;inum;i){ sstrs[0][i]; } return s; } };代码说明正确性无逻辑 bug全部用例可通过缺陷 优化点min是 C 关键字不能用作变量名规范改为minLen最短长度初始值硬编码 10000依赖题目数据范围可读性差推荐初始化为strs[0].size()内层循环两两对比冗余只需拿strs[0][i]和后面所有串对比即可无需j,j1最后拼接字符串可用substr一步截取不用循环逐个字符追加标记变量f语义模糊可改名isSame。4. 规范简化标准代码class Solution { public: string longestCommonPrefix(vectorstring strs) { int n strs.size(); int minLen strs[0].size(); // 求最短字符串长度 for (auto s : strs) { if (s.size() minLen) minLen s.size(); } int preLen 0; // 逐列纵向扫描 for (int i 0; i minLen; i) { char base strs[0][i]; bool allSame true; for (int j 1; j n; j) { if (strs[j][i] ! base) { allSame false; break; } } if (!allSame) break; preLen; } // 直接截取前缀无需循环拼接 return strs[0].substr(0, preLen); } };5. 总结你的纵向扫描思路正确是考场常用写法但变量命名、内层循环、字符串拼接存在冗余优化核心技巧以第一个字符串字符为基准和其余所有串同位置对比减少判断次数字符串截取substr(pos, len)代替循环字符拼接代码更简洁边界全覆盖单字符串、无公共前缀、最短串就是公共前缀。6. 相关知识拓展拓展 1横向扫描逐个求两个串公共前缀不断更新当前公共前缀每次和下一个字符串求交集前缀为空直接提前返回string longestCommonPrefix(vectorstring strs) { string pre strs[0]; for (auto s : strs) { int len min(pre.size(), s.size()); int idx 0; while (idx len pre[idx] s[idx]) idx; pre pre.substr(0, idx); if (pre.empty()) break; } return pre; }拓展 2排序法极简偷懒写法排序后只需比较第一个和最后一个字符串的公共前缀string longestCommonPrefix(vectorstring strs) { sort(strs.begin(), strs.end()); string a strs[0], b strs.back(); int len min(a.size(), b.size()); int i 0; while (i len a[i] b[i]) i; return a.substr(0, i); }缺点排序增加时间开销 (O(mn\log n))。拓展 3复杂度对比纵向扫描优化后(O(mn))(O(1))横向扫描(O(mn))(O(1))排序法(O(mn\log n))(O(1))。