📋 题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]仅由小写英文字母组成
🧠 解题思路
核心思想：纵向扫描法
以第一个字符串为基准，逐个字符地与其他字符串比较相同位置的字符，直到发现不匹配或某个字符串结束。
算法步骤：
边界处理：如果数组为空或为null，直接返回空字符串
选取基准：以第一个字符串作为比较的基准
逐字符比较：
遍历基准字符串的每个字符
对于每个位置，检查数组中所有字符串在该位置的字符
如果发现不匹配或某个字符串已到末尾，立即返回当前已匹配的前缀
完全匹配：如果所有字符都匹配，返回整个基准字符串
💻 代码实现
java
class Solution { public String longestCommonPrefix(String[] strs) { // 边界情况处理 if(strs == null || strs.length == 0) { return ""; } // 以第一个字符串作为比较基准 String s0 = strs[0]; // 遍历基准字符串的每个字符 for(int j = 0; j < s0.length(); j++) { char c = s0.charAt(j); // 获取基准字符串当前位置的字符 // 遍历数组中的所有字符串 for(String s : strs) { // 注意：这里要先判断索引是否越界，再比较字符 if(j == s.length() || s.charAt(j) != c) { // 发现不匹配或字符串已结束，返回已匹配的前缀 return s0.substring(0, j); } } } // 所有字符都匹配，返回整个基准字符串 return s0; } }🔍 执行过程详解
以输入["flower", "flow", "flight"]为例：
第1轮比较（j = 0）：
基准字符：
s0.charAt(0) = 'f'检查所有字符串的第0个字符：
"flower"[0] = 'f'✓"flow"[0] = 'f'✓"flight"[0] = 'f'✓
所有匹配，继续下一轮
第2轮比较（j = 1）：
基准字符：
s0.charAt(1) = 'l'检查所有字符串的第1个字符：
"flower"[1] = 'l'✓"flow"[1] = 'l'✓"flight"[1] = 'l'✓
所有匹配，继续下一轮
第3轮比较（j = 2）：
基准字符：
s0.charAt(2) = 'o'检查所有字符串的第2个字符：
"flower"[2] = 'o'✓"flow"[2] = 'o'✓"flight"[2] = 'i'✗（不匹配！）
发现不匹配，返回
s0.substring(0, 2) = "fl"
最终结果："fl"
⚡ 复杂度分析
时间复杂度：O(S)
其中 S 是所有字符串中字符的总数
在最坏情况下，算法会检查每个字符串的每个字符
但通常情况下一旦发现不匹配就会提前结束，实际运行时间通常小于 O(S)
空间复杂度：O(1)
只使用了常数级别的额外空间
没有使用额外的数据结构
🎯 关键点解析
1.边界条件处理的顺序
java
// ❌ 错误写法（可能导致数组越界） if(c != s.charAt(j) || j == s.length()) // ✅ 正确写法（利用短路原则） if(j == s.length() || s.charAt(j) != c)
重要原则：先检查索引是否有效，再访问该索引处的元素。
2.charAt()方法
用于获取字符串中指定位置的字符
索引从0开始，最大索引为
length()-1如果索引越界会抛出
StringIndexOutOfBoundsException
3.substring()方法
用于提取字符串的一部分
substring(0, j)提取索引0到j-1的字符（不包含j）当j=0时，返回空字符串
""
🔄 其他解法对比
1.横向扫描法
public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; String prefix = strs[0]; for(int i = 1; i < strs.length; i++) { while(strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if(prefix.isEmpty()) return ""; } } return prefix; }思路：将前一个字符串的公共前缀与后一个字符串比较，不断缩减前缀
时间复杂度：O(S)，其中S是所有字符串字符总数
2.分治法
public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; return divideAndConquer(strs, 0, strs.length - 1); } private String divideAndConquer(String[] strs, int left, int right) { if(left == right) return strs[left]; int mid = (left + right) / 2; String leftPrefix = divideAndConquer(strs, left, mid); String rightPrefix = divideAndConquer(strs, mid + 1, right); return commonPrefix(leftPrefix, rightPrefix); } private String commonPrefix(String str1, String str2) { int minLength = Math.min(str1.length(), str2.length()); for(int i = 0; i < minLength; i++) { if(str1.charAt(i) != str2.charAt(i)) { return str1.substring(0, i); } } return str1.substring(0, minLength); }思路：将问题分解为子问题，合并结果
时间复杂度：O(S)
优点：适合并行处理
3.二分查找法
public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; int minLength = Integer.MAX_VALUE; for(String str : strs) { minLength = Math.min(minLength, str.length()); } int left = 0, right = minLength; while(left < right) { int mid = (left + right + 1) / 2; if(isCommonPrefix(strs, mid)) { left = mid; } else { right = mid - 1; } } return strs[0].substring(0, left); } private boolean isCommonPrefix(String[] strs, int length) { String prefix = strs[0].substring(0, length); for(int i = 1; i < strs.length; i++) { if(!strs[i].startsWith(prefix)) { return false; } } return true; }思路：对前缀长度进行二分查找
时间复杂度：O(S·log m)，其中m是最短字符串长度
优点：当字符串很长时效率更高
📝 常见错误及避免方法
错误1：忘记处理空数组
java
// ❌ 错误：如果strs为空，会抛出NullPointerException String s0 = strs[0]; // ✅ 正确：先检查数组是否为空或null if(strs == null || strs.length == 0) { return ""; }错误2：索引越界
java
// ❌ 错误：可能先访问s.charAt(j)导致越界 if(s.charAt(j) != c || j == s.length()) // ✅ 正确：先检查索引是否有效 if(j == s.length() || s.charAt(j) != c)
错误3：没有考虑字符串长度不同的情况
java
// ❌ 错误：假设所有字符串长度相同 for(int j = 0; j < s0.length(); j++) { // 如果没有检查j == s.length()，当s较短时会越界 } // ✅ 正确：在比较字符前检查字符串长度 if(j == s.length() || s.charAt(j) != c)🏆 总结
本文介绍的纵向扫描法是最直观且高效的解法，具有以下优点：
代码简洁：仅需10余行代码即可实现
逻辑清晰：逐字符比较的思路容易理解
效率高：一旦发现不匹配立即返回，避免不必要的比较
空间优：只使用常数级别的额外空间
关键技巧：
以第一个字符串为基准
利用短路原则避免索引越界
使用
substring()返回已匹配的前缀
掌握这种方法不仅能解决最长公共前缀问题，其中的思想（逐位比较、提前终止）也能应用于其他字符串处理问题中。
)