[LeetCode]最长公共前缀（Longest Common Prefix）

共计 1311 个字符，预计需要花费 4 分钟才能阅读完成。

题目描述
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
示例 1: 输入: [“flower”,”flow”,”flight”] 输出: “fl” 示例 2: 输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z。

解决方法
横向匹配所有字符串
取出字符串数组里任意一个字符串 prefix，遍历其余的字符串判断 prefix 是否是其的前缀，不是就去掉 prefix 最后一个字符，直到 prefix 为空
public String longestCommonPrefix(String[] strs) {
if (strs == null || 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.isEmpty())
return “”;
}
}

return prefix;
}
时间复杂度：O(S)，其中 S 是所有字符串中所有字符的总和空间复杂度：O(1)，只使用了恒定的额外空间
二分搜索

取最短的字符串的长度 minLen 作为右边界 right，因为最长公共前缀的长度不可能大于字符串数组里最短字符串的长度
判断左半部分是否是公共前缀，是的话向右寻找更长的公共前缀，反之向左寻找公共前缀
当 左边界 left > 右边界 right 寻找结束，最长公共前缀范围就是 [0, (left + right) / 2)

public String longestCommonPrefix2(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 left = 1, right = minLen;
while (left <= right) {
int middle = (left + right) / 2;
if (isCommonPrefix(strs, middle))
left = middle + 1;
else
right = middle – 1;
}

return strs[0].substring(0, (left + right) / 2);
}

public 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;
}
时间复杂度：O(S*log(n))，其中 S 是所有字符串中所有字符的总和。空间复杂度：O(1)。我们只使用了恒定的额外空间。
本文首发：https://lierabbit.cn/2018/05/…