24b695a430945c421d89577af1d17e68
(难度Easy)Problem 14. Longest Common Prefix

(难度Easy)Problem 14. Longest Common Prefix

链接

https://leetcode.com/problems/longest-common-prefix/

难度等级

Easy

题干

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

If there is no common prefix, return an empty string "".

题意

给定一系列字符串,查找这些字符串的最长公共前缀

样例

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

题解

解法一 单值维护

先说比较容易想到的方法,就是维护一个之前出现过的最长公共前缀。

我们都知道两个字符串求最长公共前缀没什么好的办法,只有遍历一位一位地比对。当我们有n个字符串的时候,应该怎么办呢?很简单,我们先求出S0和S1的最长公共前缀L1,然后将L和S2进行比对,求出最长公共前缀L2。再将L2和S3匹配,依次类推,最终求出Ln。

写成伪代码如下:

l = LCP(s[0], s[1])
for i in range(n):
    l = LCP(l, s[i])
return l

伪代码中的LCP指的就是计算两个字符串最长公共前缀的过程,其实就是一个简单的遍历,相信以大家的能力应该都能写出来。

那么这个算法的复杂度是多少呢?

简单分析一下,不难发现,是O(S),这里的S指的是所有字符串的长度总和。因为极端情况下我们需要把所有的字符串当中的所有字符都遍历一遍(比如当所有字符串都相同的时候)。

总体来说这个方法实现简单,复杂度也不错,美中不足的就是技术含量低了一点。

推荐指数:☆☆☆

解法二 垂直扫描

这个名称是我从LeetCode里看来的,因为我真的不知道这种算法应该叫什么。

其实它和解法一刚好相反,解法一是通过两两比对不停地更新答案,最终获得最终解。而垂直扫描是直接求解答案,怎么求解呢?

其实很简单,我们一个字符一个字符的判断。如果所有的字符串的该位置的字符都相同,说明这个字符满足条件,可以被加入答案当中。如果不是,说明我们已经找到了答案,就可以终止了。

写成伪代码也很简单:

for i in range(len(s0)):
    for st in s:
        if st[i] != s[0][i]:
            flag = false
            break
    if !flag:
        break
    ret = ret + s[0][i]

这种解法的复杂度也是O(S),但是其实仔细分析起来是比解法一稍稍好一些的。虽然从量级上两者是相同的,但是解法一对于部分字符串完全相同的情况不是特别友好,而解法二就不会有这个问题。一视同仁,不会因为部分字符串出现特殊值而受影响。

top Created with Sketch.