題目
編寫(xiě)一個(gè)函數(shù)來(lái)查找字符串?dāng)?shù)組中的最長(zhǎng)公共前綴。
如果不存在公共前綴，返回空字符串 ""必怜。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴蚯涮。說(shuō)明:
所有輸入只包含小寫(xiě)字母
a-z。來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-common-prefix
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有褥傍。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處喇聊。
解法1：
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs==null||strs.length==0) return "";
return longest(strs,0,strs.length-1);
}
public String longest(String[] strs, int start, int end){
if(start==end){
return strs[start];
}
int mid=(end+start)/2;
String leftstr=longest(strs,start,mid);
String rightstr=longest(strs,mid+1,end);
return judge(leftstr,rightstr);
}
public String judge(String leftstr,String rightstr){
int n = Math.min(leftstr.length(),rightstr.length());
for(int i = 0 ; i < n; i++){
while(leftstr.charAt(i)!=rightstr.charAt(i)){
return leftstr.substring(0,i);
}
}
return leftstr.substring(0,n);
}
}
