14. Longest Common Prefix (最长公共前缀)

问题描述

英文

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.

Note:

All given inputs are in lowercase letters a-z.

中文

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

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

示例 1:

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

示例 2:

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

说明:

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

Solution

Python

Method 1：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        string = ''
        
        if not strs:
            return ''
        elif len(strs) == 1:
            return strs[0]
        else:
            min_len = min([len(i) for i in strs])
            flag = True
            for n in range(min_len):
                tmp = strs[0][n]
                for m in range(1, len(strs)):
                    if strs[m][n] != tmp:
                        flag = False
                if flag:
                    string = string + tmp
            return string

Submissions

执行用时 : 80 ms, 在Longest Common Prefix的Python3提交中击败了4.74% 的用户

内存消耗 : 13.2 MB, 在Longest Common Prefix的Python3提交中击败了0.98% 的用户