LeetCode | 5. Longest Common Prefix 最长公共前缀

用户头像
Puran
关注
发布于: 2020 年 06 月 20 日
LeetCode | 5. Longest Common Prefix 最长公共前缀

Longest Common Prefix 是 LeetCode 算法题库中的第十四道题,难度为 Easy,题目地址为:https://leetcode.com/problems/longest-common-prefix/



1. 问题描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回空字符串""。(所有输入都只包含小写字母a-z



示例:

Input: [“flower”,”flow”,”flight”]
Output: “fl”

2. 解题思路

看到该题,我首先想到的是分别取每个字符串的相同位置的字符进行一一比较,这其实是纵向扫描方法。



该题官方是给出了4种解题思路,分别是:

  1. 纵向扫描:从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。

  2. 横向扫描:依次遍历每个字符串,对于每个字符串,更新最长公共前缀,当遍历完所有字符串以后,就可以得到最长公共前缀了。该方法是基于这样的基础:

  3. 分治:类似于横向扫描方法,将字符串数组分为拆成两个子部分来计算最长公共前缀。

  4. 二分查找:通过找到字符串数组中的最短数组,以这个字符串的长度为基础取得中间值mid,判断每个字符串的长度为mid 的前缀是否相同。

3. 知识点

这里的知识点包括两个算法概念,以后再来做更为详细的学习:

  • 分治

  • 二分查找



对 C# 的语言,来求取字符串的切片时,可以通过 String.Substring方法

4. 代码



Python 实现

  • 纵向扫描

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
length, count = len(strs[0]), len(strs)
for i in range(length):
c = strs[0][i]
for j in range(1, count):
if (i == len(strs[j]) or strs[j][i] != c):
return strs[0][:i]
return strs[0]



  • 横向扫描

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
prefix, count = strs[0], len(strs)
for i in range(1, count):
prefix = self.lcp(prefix, strs[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]



  • 分治

class Solution:
def longestCommonPrefix(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)





C# 实现

  • ‍纵向扫描

public class Solution {
public string LongestCommonPrefix(string[] strs) {
if (strs == null || strs.Length == 0)
return "";
int length = strs[0].Length;
int count = strs.Length;
string prefix = strs[0];
for (int i = 0; i < length; i++)
{
char c = strs[0][i];
for (int j = 0; j < count; j++)
{
if (i == strs[j].Length || strs[j][i] != c)
{
prefix = prefix.Substring(0, i);
return prefix;
}
}
}
return prefix;
}
}



  • ‍横向扫描

public class Solution {
public string LongestCommonPrefix(string[] strs) {
if (strs == null || strs.Length == 0)
return "";
int count = strs.Length;
string prefix = strs[0];
for (int i = 1; i < count; i++)
{
prefix = lcp(prefix, strs[i]);
}
return prefix;
}
string lcp(string str1, string str2)
{
int length = Math.Min(str1.Length, str2.Length);
int index = 0;
while (index < length && str1[index] == str2[index])
{
++index;
}
return str1.Substring(0, index);
}
}





发布于: 2020 年 06 月 20 日 阅读数: 64
用户头像

Puran

关注

GIS从业者,正在往开发的路上小跑。 2018.03.29 加入

从业4年的GIS开发小白,work@esri。

评论

发布
暂无评论
LeetCode | 5. Longest Common Prefix 最长公共前缀