Skip to main content

14. 最长公共前缀[simple]

14. 最长公共前缀[simple]​

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

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

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

通过次数258,774 提交次数693,157

Second Try​

2020-06-05

利用zip函数加快便利，如果熟悉zip函数一切都很自然。 看题解还有使用trie树的，先刷一波后再详细学习题解吧。

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ""
        rv = ""
        for tup in zip(*strs):
            if len(set(tup)) != 1:
                break
            rv += tup[0]
        return rv

  • zip 函数
In [23]: zip?
Init signature: zip(self, /, *args, **kwargs)
Docstring:
zip(iter1 [,iter2 [...]]) --> zip object

Return a zip object whose .__next__() method returns a tuple where
the i-th element comes from the i-th iterable argument.  The .__next__()
method continues until the shortest iterable in the argument sequence
is exhausted and then it raises StopIteration.
Type:           type

In [24]: x
Out[24]: ['abc', 'ef', 'kg']

In [25]: for tup in zip(*x):
    ...:     print(tup)
    ...:
('a', 'e', 'k')
('b', 'f', 'g')

  • 执行用时 :24 ms, 在所有 Python 提交中击败了63.66%的用户
  • 内存消耗 :13 MB, 在所有 Python 提交中击败了5.88%的用户

First Try​

2020-06-05

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs:
            return ""

        rv = ""
        i = 0
        break_iter = False
        while not break_iter:
            if i > len(strs[0]) - 1:
                break_iter = True
            else:
                c = strs[0][i]
                for item in strs:
                    if i > len(item) - 1:
                        break_iter = True
                        break
                    if item[i] != c:
                        break_iter = True
                        break
                if not break_iter:
                    rv += c
                    i += 1
        return rv

执行用时 :20 ms, 在所有 Python 提交中击败了83.58%的用户 内存消耗 :12.7 MB, 在所有 Python 提交中击败了5.88%的用户