JAVA练习371- 最长公共前缀

题目概览

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]如果非空，则仅由小写英文字母组成

来源：14. 最长公共前缀 - 力扣（LeetCode）

解题分析

方法一：纵向遍历

纵向遍历是最直观的解法。从每个字符串的第一个字符开始，依次比较同一列上的字符是否相同。

算法步骤：

1. 以第一个字符串strs[0]为基准，遍历其每个字符（索引j）。
2. 对于每个索引j，遍历数组中其余字符串（strs[1]到strs[n-1]）。
3. 如果遇到以下情况之一，则停止遍历并返回结果：
   • 当前字符串strs[i]的长度小于等于j（即该字符串已到末尾）。
   • 当前字符串在索引j处的字符与基准字符串strs[0]在索引j处的字符不同。
4. 如果遍历完基准字符串的所有字符都未遇到不匹配，则整个基准字符串就是最长公共前缀。

复杂度分析：

• 时间复杂度：O(m×n)，其中 m 是字符串的平均长度，n 是字符串数组的长度。最坏情况下需要比较所有字符。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } // 以第一个字符串为基准 for (int j = 0; j < strs[0].length(); j++) { char c = strs[0].charAt(j); // 遍历其余字符串 for (int i = 1; i < strs.length; i++) { // 如果当前字符串长度不足或字符不匹配 if (j >= strs[i].length() || strs[i].charAt(j) != c) { return strs[0].substring(0, j); } } } // 第一个字符串本身就是最长公共前缀 return strs[0]; } }

方法二：横向扫描

横向扫描是另一种常见思路：依次将每个字符串与当前得到的前缀进行比较，并更新前缀。

算法步骤：

1. 将第一个字符串strs[0]作为初始前缀prefix。
2. 遍历数组中的每个字符串strs[i]（从第二个开始）：
   • 比较prefix与strs[i]，找出它们的最长公共前缀。
   • 将prefix更新为这个新的前缀。
   • 如果prefix变为空字符串，则提前返回""。
3. 遍历结束后，prefix即为最长公共前缀。

复杂度分析：

• 时间复杂度：O(m×n)，其中 m 是字符串的平均长度，n 是字符串数组的长度。
• 空间复杂度：O(m)，需要存储当前前缀。

class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } String prefix = strs[0]; for (int i = 1; i < strs.length; i++) { // 找出 prefix 与当前字符串的公共前缀 while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) { return ""; } } } return prefix; } }

方法三：分治法

将问题分解为子问题：数组的最长公共前缀 = 左半部分的最长公共前缀 与 右半部分的最长公共前缀 的公共前缀。

算法步骤：

1. 将字符串数组分成左右两半。
2. 递归求出左半部分的最长公共前缀leftPrefix。
3. 递归求出右半部分的最长公共前缀rightPrefix。
4. 返回leftPrefix和rightPrefix的公共前缀。
5. 递归的基准情况：当区间只有一个字符串时，直接返回该字符串。

复杂度分析：

• 时间复杂度：O(m×n)，与纵向遍历相同，但递归调用会带来额外的开销。
• 空间复杂度：O(m×log n)，递归深度为 log n，每层需要存储中间结果。

class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } return divide(strs, 0, strs.length - 1); } private String divide(String[] strs, int left, int right) { if (left == right) { return strs[left]; } int mid = left + (right - left) / 2; String leftPrefix = divide(strs, left, mid); String rightPrefix = divide(strs, mid + 1, right); return commonPrefix(leftPrefix, rightPrefix); } private String commonPrefix(String str1, String str2) { int minLen = Math.min(str1.length(), str2.length()); for (int i = 0; i < minLen; i++) { if (str1.charAt(i) != str2.charAt(i)) { return str1.substring(0, i); } } return str1.substring(0, minLen); } }

方法对比与总结

推荐：在实际面试或编程中，纵向遍历是最常用且高效的解法，代码简洁，空间复杂度最优。

边界情况处理：

• 输入数组为空或为null：直接返回空字符串。
• 数组中包含空字符串：公共前缀必然为空。
• 所有字符串完全相同：返回任意一个字符串。