public String longestCommonPrefix(String[] strs, int index){ if (index == strs.length - 1) { return strs[index]; } // 递归处理当前字符串和(后续所有字符传最长公共前缀)的最长公共前缀。 return longestCommonPrefixTwoStr(strs[index], longestCommonPrefix(strs, index + 1)); }
public String longestCommonPrefixTwoStr(String str1, String str2){ int len = Math.min(str1.length(), str2.length()); int index = 0; while (index < len && str1.charAt(index) == str2.charAt(index)) { index++; } return str1.substring(0, index); }
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 = longestCommonPrefixTwoStr(prefix, strs[i]); if (prefix.length() == 0) { break; } } return prefix; }
public String longestCommonPrefixTwoStr(String str1, String str2){ int len = Math.min(str1.length(), str2.length()); int index = 0; while (index < len && str1.charAt(index) == str2.charAt(index)) { index++; } return str1.substring(0, index); }
复杂度分析
时间复杂度:O(mn),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。最坏情况下,字符串数组中的每个字符串的每个字符都会被比较一次。
public String longestCommonPrefix(String[] strs, int start, int end){ if (start == end) { return strs[start]; } else { int mid = (end - start) / 2 + start; String left = longestCommonPrefix(strs, start, mid); String right = longestCommonPrefix(strs, mid + 1, end); return longestCommonPrefixTwoStr(left, right); } }
public String longestCommonPrefixTwoStr(String str1, String str2){ int len = Math.min(str1.length(), str2.length()); int index = 0; while (index < len && str1.charAt(index) == str2.charAt(index)) { index++; } return str1.substring(0, index); }
复杂度分析
时间复杂度:O(mn),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。时间复杂度的递推式是 T(n)=2⋅T(n/2)+O(m),通过计算可得 T(n)=O(mn)。
空间复杂度:O(mlogn),其中 m 是字符串数组中的字符串的平均长度,n 是字符串的数量。空间复杂度主要取决于递归调用的层数,层数最大为 logn,每层需要 m 的空间存储返回结果。