14. 最长公共前缀
2019-07-14 本文已影响0人
爱情小傻蛋
一、题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
二、解法
2.1方法一:水平扫描法
public static String longestCommonPrefix(String[] strs) {
if (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.length() == 0){
return "";
}
}
}
return prefix;
}
2.2方法二:分治法
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return longestCommonPrefix(strs, 0 , strs.length - 1);
}
private String longestCommonPrefix(String[] strs, int l, int r) {
if (l == r) {
return strs[l];
}
else {
int mid = (l + r)/2;
String lcpLeft = longestCommonPrefix(strs, l , mid);
String lcpRight = longestCommonPrefix(strs, mid + 1,r);
return commonPrefix(lcpLeft, lcpRight);
}
}
String commonPrefix(String left,String right) {
int min = Math.min(left.length(), right.length());
for (int i = 0; i < min; i++) {
if ( left.charAt(i) != right.charAt(i) )
return left.substring(0, i);
}
return left.substring(0, min);
}