当前位置：首页 > news >正文

力扣14.最长公共前缀-纵向扫描法

news 2026/3/27 3:18:15

📋 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串""。

示例 1：

输入：strs = ["flower","flow","flight"] 输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[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)