Write a function to find the longest common prefix string amongst an array of strings.
1. 解法一
思路
对字符串数组进行排序，比较第一个字符串和最后一个字符串的公共前缀
代码
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
strs.sort()
for i in range(min(len(strs[0]), len(strs[-1]))):
if strs[0][i] != strs[-1][i]:
return strs[0][0:i]
return strs[0]
解法二
思路
从长度入手，利用二分法不断寻找最大的公共前缀的长度。
public class Solution{
public String longestCommonPrefix(String[] strs){
if(strs == null || strs.length == 0){
return "";
}
int minLen = Integer.MAX_VALUE;
for (String str:strs) {
minLen = Math.min(minLen, str.length());
}
int low = 0;
int high = minLen;
while (low <= high) {
int mid = (low + high) / 2;
if (isPrefix(strs, mid)) {
low = mid + 1;
}else{
high = mid - 1;
}
}
return strs[0].substring(0, (low+high)/2);
}
private boolean isPrefix(String[] strs, int len){
String str1 = strs[0].substring(0, len);
for(int i= 1; i < strs.length; i++){
if(!strs[i].startsWith(str1)){
return false;
}
}
return true;
}
}
