Leetcode 14 Longest Common Prefix

发表于 |

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

说明:
所有输入只包含小写字母 a-z 。

题意分析：
需要找到一个最长的字符串，使得这个字符串是数组中所有字符的公共前缀。

思路分析：
如果你是看我题解比较多的人，应该看到我题意分析中的语句可能就已经懂了这道题要怎么做了。
找一个数，使这个数满足某种条件，符合这种描述的题型，极有可能是二分法。

这道题也不例外，因为前缀最长也只能是数组中最短的字符串ss的长度，我们只需要判断到底要在ss中选择多长的前缀即可。

对于我们每次选择的长度，我们判断其到底是不是数组中每个字符的前缀，如果是，说明最后的结果长度可能更长；反之，说明结果长度不够。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 24ms, beats 88.14%
class Solution(object):
    def longestCommonPrefix(self, s):
        if not s: return ''
        ss = min(s, key=len)
        def isPre(s,ss,mid):
            pre = ss[:mid]
            if all(e.startswith(pre) for e in s): return True
            return False

        l,r = 0,len(ss)
        while l < r-1:
            mid = (l+r) // 2
            if isPre(s,ss,mid):
                l = mid
            else:
                r = mid-1
        if isPre(s,ss,r): return ss[:r]
        return ss[:l]