题目链接：https://leetcode.com/problems/longest-common-prefix/description/
这道题我的思路还好，想出了两种实现，也凑活着写出了它们的实现。下面是我自己的思路实现以及官方方法的实现源码了：
import java.util.Arrays;
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
String[] strs = {"cab", "ccc", "cdc"};
System.out.println("strs = " + Arrays.toString(strs) + ", longestCommonPrefix = " + longestCommonPrefix(strs));
System.out.println("strs = " + Arrays.toString(strs) + ", longestCommonPrefix = " + longestCommonPrefix2(strs));
System.out.println("strs = " + Arrays.toString(strs) + ", longestCommonPrefix = " + longestCommonPrefix3(strs));
}
/**
* 我的方法一：最简单的逐级遍历
*
* 时间复杂度：O(n)
*
* 运行详情：
* 1. Runtime：12ms
* 2. Your runtime beats 34.01% of java submissions.
*
* @param strs 目标字符串数组
* @return 最长公共前缀
*/
public static String longestCommonPrefix(String[] strs) {
if (strs.length < 1) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
String firstStr = strs[0];
String longestCommonPrefix = "";
boolean isOk = true;
for (int i = 0; i <= firstStr.length() && isOk; i++) {
longestCommonPrefix = firstStr.substring(0, i);
for (int j = 1; j < strs.length; j++) {
if (!strs[j].startsWith(longestCommonPrefix)) {
isOk = false;
break;
}
}
}
if (!"".equals(longestCommonPrefix) && !isOk) {
longestCommonPrefix = longestCommonPrefix.substring(0, longestCommonPrefix.length() - 1);
}
return longestCommonPrefix;
}
/**
* 我的方法二：分治 + 递归
*
* 时间复杂度：O(logn)
*
* 运行详情：
* 1. Runtime：15ms
* 2. Your runtime beats 11.58% of java submissions.
*
* Note：这里使用了分治 + 递归的方法，照理说运行时间应该是降低了的，我想运行时间不降反升的原因可能是递归里面频繁使用了
* new String[] 导致的吧！
*
* @param strs 目标字符串数组
* @return 最长公共前缀
*/
public static String longestCommonPrefix2(String[] strs) {
if (strs.length == 0) {
return "";
}
return longestCommonPrefix2Handler(strs, 0, strs.length - 1);
}
// longestCommonPrefix2 的辅助方法
public static String longestCommonPrefix2Handler(String[] strs, int start, int end) {
if (start == end) {
return strs[start];
}
if (end - start == 1) {
String startStr = strs[start];
String endStr = strs[end];
if ("".equals(startStr) || "".equals(endStr)) {
return "";
}
int i = 0;
boolean flag = true;
for (; i < startStr.length() && i < endStr.length(); i++) {
if (startStr.charAt(i) != endStr.charAt(i)) {
flag = false;
break;
}
}
if (flag) {
return startStr.length() > endStr.length() ? endStr : startStr;
} else {
return startStr.substring(0, i);
}
}
String left = longestCommonPrefix2Handler(strs, start, (start + end) / 2);
String right = longestCommonPrefix2Handler(strs, (start + end) / 2 + 1, end);
return longestCommonPrefix2Handler(new String[]{left, right}, 0, 1);
}
/**
* 官方方法一：Horizontal scanning
*
* 运行详情：
* 1. Runtime：12ms
* 2. Your runtime beats 34.01% of java submissions.
*
* Note: 这个方法跟我的方法一思路差不多是一样的，不过大神写的代码就是思路清晰，代码简洁！
*
* @param strs
* @return
*/
public static String longestCommonPrefix3(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) { // 这里使用了 String.indexOf 方法不太好理解哦，其实这句话的意思就是 while(strs[i].startsWith(prefix)) { ... }
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}
/**
* 官方方法二：Vertical scanning
*
* 运行详情：
* 1. Runtime：11ms
* 2. Your runtime beats 49.68% of java submissions.
*
* Note：没看到这种方法为啥要叫 Vertical scanning，我觉得还是 Horizontal scanning 啊！
*
* @param strs
* @return
*/
public static String longestCommonPrefix4(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length() ; i++){
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j ++) {
if (i == strs[j].length() || strs[j].charAt(i) != c)
return strs[0].substring(0, i);
}
}
return strs[0];
}
/**
* 官方方法三：分治法
*
* 运行详情：
* 1. Runtime：13ms
* 2. Your runtime beats 23.01% of java submissions.
*
* Note：哈哈，官方竟然也有分治法，看来开始我的思路都还算正确啊！不过，不得不说官方的代码都是很简洁的。。。而且还很明智的避免了在递归
* 里反复使用 new String[] 的语句！不过从运行详情上来看，官方的递归分治方法运行时间也是比前两种方法要慢啊！
*
* @param strs
* @return
*/
public String longestCommonPrefix5(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);
}
/**
* 官方方法四：使用二分法来优化 Horizontal scanning 和 Vertical scanning
*
* 运行详情：
* 1. Runtime：9ms
* 2. Your runtime beats 85.23% of java submissions.
*
* Note：Horizontal scanning 方法是从后向前遍历字符串的每个字符，Vertical scanning 方法是从前向后遍历字符串的每个字符。然而，这
* 个方法六又把二分法融合进来，肯定是极大提高效率了，真是生命不息，优化不止啊！
*
* @param strs
* @return
*/
public String longestCommonPrefix6(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 = 1;
int high = minLen;
while (low <= high) {
int middle = (low + high) / 2;
if (isCommonPrefix(strs, middle))
low = middle + 1;
else
high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);
}
private boolean isCommonPrefix(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;
}
// 进一步的思考就是使用字典树（即前缀树）了！
}