JAVA：
package com.leetcode;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Hot014_LongestCommonPrefix {
// -----------------------------------Solution1:横向扫描----------------------------------
public String longestCommonPrefix(String[] strs) {
// CHECK parameter
if (strs == null || strs.length == 0)
return "";
// ToLowerCase 因为题意仅由小写英文字母组成 , 可省略
List list = Arrays.stream(strs).map(String::toLowerCase).collect(Collectors.toList());
strs = list.toArray(new String[list.size()]);
// System.out.println(Arrays.toString(strs));
// 设第一个字符串是最大公共前缀
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
// 公共前缀
prefix = longestCommonPrefix(prefix, strs[i]);
if (prefix.length() == 0) {
break;
}
}
return prefix;
}
private String longestCommonPrefix(String str1, String str2) {
int length = Math.min(str1.length(), str2.length());
int index = 0;
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++;
}
return str1.substring(0, index);
}
// -----------------------------------Solution2:纵向扫描----------------------------------
public String longestCommonPrefix2(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++) {
// i是最后一个字符时 或者 遍历到的字符串的 i位置的字符 不是 第一个串的 （不一样时 ） 退出内循环
if (i == strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
// -----------------------------------Solution3:分治----------------------------------
public String longestCommonPrefix3(String[] strs) {
if (strs == null || strs.length == 0)
return "";
return longestCommonPrefix3(strs, 0, strs.length - 1);
}
private String longestCommonPrefix3(String[] strs, int start, int end) {
// BASE CASE
if (start == end)
return strs[start];
// CASE 1: 二分
int mid = (end - start) / 2 + start;
String lcpLeft = longestCommonPrefix3(strs, start, mid);
String lcpRight = longestCommonPrefix3(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
private String commonPrefix(String str1, String str2) {
// 获取两比较字符串的 最小 长度
int minLength = Math.min(str1.length(), str2.length());
for (int i = 0; i < minLength; ++i) {
if (str1.charAt(i) != str2.charAt(i))
return str1.substring(0, i);
}
return str1.substring(0, minLength);
}
// -----------------------------------Solution4:二分查找----------------------------------
public String longestCommonPrefix4(String[] strs) {
if (strs == null || strs.length == 0)
return "";
// 得到strs中 最短的 str的长度
int minLength = Integer.MAX_VALUE;
for (String str : strs)
minLength = Math.min(minLength, str.length());
// 二分
int low = 0, high = minLength;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (isCommonPrefix(strs, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return strs[0].substring(0, low);
}
private boolean isCommonPrefix(String[] strs, int length) {
// 获取前缀
String str0 = strs[0].substring(0, length);
// 遍历所有的 字符
for (int i = 1; i < strs.length; i++) {
String str = strs[i];
// 判断 前缀 是否符合 当前 字符
for (int j = 0; j < length; j++) {
if (str0.charAt(j) != str.charAt(j)) {
return false;
}
}
}
return true;
}
// ----------------------------------- main ----------------------------------
public static void main(String[] args) {
String[] strs = { "flower", "flow", "flight" };
System.out.println("-");
System.out.println(new Hot014_LongestCommonPrefix().longestCommonPrefix(strs));
System.out.println("-");
System.out.println(new Hot014_LongestCommonPrefix().longestCommonPrefix2(strs));
System.out.println("-");
System.out.println(new Hot014_LongestCommonPrefix().longestCommonPrefix3(strs));
System.out.println("-");
System.out.println(new Hot014_LongestCommonPrefix().longestCommonPrefix4(strs));
System.out.println("-");
}
}
Python3：
# -*- coding = utf-8 -*-
# @Time : 2022/05/11 19:05
# @Author : butupi
# @File : h14_LongestCommonPrefix.py
# @Software : PyCharm
from typing import List
class Solution:
# 方法一：横向扫描
def longestCommonPrefix(self, strs: List[str]) -> str:
# CHECK parameter
if not strs:
return ""
prefix, count = strs[0], len(strs)
for i in range(1, count):
prefix = self.lcp(prefix, str[i])
# 前缀为空时，跳出循环
if not prefix:
break
return prefix
def lcp(self, str1, str2):
length, index = min(len(str1), len(str2)), 0
while index < length and str1[index] == str2[index]:
index += 1
return str1[:index]
# 方法二：纵向扫描
def longest_common_prefix(self, strs: List[str]) -> str:
if strs is None:
return ""
length, count = len(strs[0]), len(strs)
for i in range(length):
c = str[0][i]
if any(i == len(strs[j]) or strs[j][i] != c for j in range(1, count)):
return strs[0][:i]
return strs[0]
# 方法三：分治
def longest_common_prefix2(self, strs: List[str]) -> str:
def lcp(start, end):
if start == end:
return strs[start]
# 分治
mid = (start + end) // 2
lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
# 取最长前缀
minLength = min(len(lcpLeft), len(lcpRight))
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
return lcpLeft[:i]
return lcpLeft[:minLength]
return "" if not strs else lcp(0, len(strs) - 1)
# 方法四：二分
def longest_common_prefix3(self, strs: List[str]) -> str:
# 是否是公共前缀
def is_common_prefix(length):
str0, count = strs[0][:length], len(strs)
return all(str[i][:length] == str0 for i in range(1, count))
if not strs:
return ""
min_length = min(len(s) for s in strs)
low, high = 0, min_length
while low < high:
mid = (high - low + 1) // 2 + low
if is_common_prefix(mid):
low = mid
else:
high = mid - 1
return strs[0][:low]
if __name__ == "__main__":
strs = ["hello", "helli", "hell"]
print(Solution().longest_common_prefix2(strs))
