JAVA练习371- 最长公共前缀

题目概览编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀返回空字符串。示例 1输入strs [flower,flow,flight] 输出fl示例 2输入strs [dog,racecar,car] 输出 解释输入不存在公共前缀。提示1 strs.length 2000 strs[i].length 200strs[i]如果非空则仅由小写英文字母组成来源14. 最长公共前缀 - 力扣LeetCode解题分析方法一纵向遍历纵向遍历是最直观的解法。从每个字符串的第一个字符开始依次比较同一列上的字符是否相同。算法步骤以第一个字符串strs[0]为基准遍历其每个字符索引j。对于每个索引j遍历数组中其余字符串strs[1]到strs[n-1]。如果遇到以下情况之一则停止遍历并返回结果当前字符串strs[i]的长度小于等于j即该字符串已到末尾。当前字符串在索引j处的字符与基准字符串strs[0]在索引j处的字符不同。如果遍历完基准字符串的所有字符都未遇到不匹配则整个基准字符串就是最长公共前缀。复杂度分析时间复杂度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]; } }方法二横向扫描横向扫描是另一种常见思路依次将每个字符串与当前得到的前缀进行比较并更新前缀。算法步骤将第一个字符串strs[0]作为初始前缀prefix。遍历数组中的每个字符串strs[i]从第二个开始比较prefix与strs[i]找出它们的最长公共前缀。将prefix更新为这个新的前缀。如果prefix变为空字符串则提前返回。遍历结束后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; } }方法三分治法将问题分解为子问题数组的最长公共前缀 左半部分的最长公共前缀 与 右半部分的最长公共前缀 的公共前缀。算法步骤将字符串数组分成左右两半。递归求出左半部分的最长公共前缀leftPrefix。递归求出右半部分的最长公共前缀rightPrefix。返回leftPrefix和rightPrefix的公共前缀。递归的基准情况当区间只有一个字符串时直接返回该字符串。复杂度分析时间复杂度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); } }方法对比与总结方法思路时间复杂度空间复杂度适用场景纵向遍历逐列比较字符O(m×n)O(1)最直观代码简洁内存占用少横向扫描依次与前缀比较并更新O(m×n)O(m)易于理解适合字符串长度差异大的情况分治法递归分解问题O(m×n)O(m×log n)适合并行计算或作为算法练习推荐在实际面试或编程中纵向遍历是最常用且高效的解法代码简洁空间复杂度最优。边界情况处理输入数组为空或为null直接返回空字符串。数组中包含空字符串公共前缀必然为空。所有字符串完全相同返回任意一个字符串。