### 题目

Write a function to find the longest common prefix string amongst an array of strings.

Ex: For aaabbb and aaaccc, their common prefix is aaa

### 暴力遍历 $O(mn)$

#### 代码

public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) { return ""; }
if (strs.length == 1) { return strs[0]; }
int maxLen = Integer.MAX_VALUE;
for (String str : strs) {
maxLen = Math.min(maxLen,str.length());
}
outerFor:
for (int i = 0; i < maxLen; i++) {
char c = strs[0].charAt(i);
for (String str : strs) {
if (str.charAt(i) != c) {
return strs[0].substring(0,i);
}
}
}
return strs[0].substring(0,maxLen);
}
}


### 递归分治二分查找 $O(n\log{}{n})$

#### 代码

public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) { return ""; }
if (strs.length == 1) { return strs[0]; }
int maxLen = Integer.MAX_VALUE;
for (String str : strs) { // 每层递归代价： O(n)
maxLen = Math.min(maxLen,str.length());
}
return longestCommonPrefixRecursive(strs,0,maxLen-1);
}
private String longestCommonPrefixRecursive(String[] strs, int low, int high) {
System.out.println("low = " + low + ", high = " + high);
// base case
if (high - low < 0) {
return "";
}
int median = low + ((high-low)/2);
char c = strs[0].charAt(median);
for (String str : strs) {
if (str.charAt(median) != c) {
return longestCommonPrefixRecursive(strs,low,median-1);
}
}
String leftPrefix = longestCommonPrefixRecursive(strs,low,median-1);
if (leftPrefix.length() == (median-low) || (median - low) < 0) {
return leftPrefix + c + longestCommonPrefixRecursive(strs,median+1,high);
} else {
return leftPrefix;
}
}
}


### 利用库函数indexOf() $O(m^2n^2)$

#### 代码

public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) { return ""; }
if (strs.length == 1) { return strs[0]; }
outerFor:
for (int i = strs[0].length() ; i > 0; i--) {
innerFor:
for (int j = 1; j < strs.length; j++) {
if (strs[j].indexOf(strs[0].substring(0,i)) != 0) { continue outerFor; }
}
return strs[0].substring(0,i);
}
return "";
}


### 排序只比较首尾元素

aaa
aaabbb
aaabc
aaaccccc


#### 代码

public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) { return ""; }
if (strs.length == 1) { return strs[0]; }
Arrays.sort(strs);
char[] first = strs[0].toCharArray();
char[] last = strs[strs.length-1].toCharArray();
int length = Math.min(first.length,last.length);
for (int i = 0; i < length; i++) {
if (first[i] != last[i]) { return new String(Arrays.copyOf(first,i)); }
}
return new String(Arrays.copyOf(first,length));
}
}