字符串数组最长公共前缀

mrli2016 发布于2019-07-25 12:04 / 2775人阅读

摘要：字符串数组最长公共前缀给出字符串数组，查找这个数组中所有字符串的最长公共前缀思路从开始自增，判断每个字符串位置的字符是否一致，不一致则之前的串为最长公共字符串。利用函数的特点返回可迭代的对象，只要判断长度大于，则表明此元素非公共字符。

字符串数组最长公共前缀 Longest Common Prefix

给出字符串数组，查找这个数组中所有字符串的最长公共前缀

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

example 1

input: ["asdqowi","asdb", "asdmnc"]
output: "asd"

思路

i从0开始自增，判断每个字符串 i 位置的字符是否一致，不一致则 i 之前的串为最长公共字符串。

利用python zip函数的特点：

a = [1, 2, 3]
b = [4, 5, 6]
c = [7, 8, 9, 10]
zip(a, b, c) is =>
(1, 4, 7)

(2, 5, 8)

(3, 6, 9)
set((1, 1, 1)) = {"1"}
set((1, 1, 2)) = {"1", "2"}

zip(*strs)返回可迭代的zip对象，只要判断set(item)长度大于0，则表明此元素非公共字符。

下面给出两种算法的代码。

代码

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        prefix = ""
        i = 0
        while True:
            try:
                tmp = strs[0][i]
                for item in strs:
                    if item[i] != tmp:
                        return prefix
            except: #out of index range，表明遍历最短字符串完毕
                return prefix
            prefix += tmp
            i += 1
        return prefix


    def longestCommonPrefix_use_zip(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        prefix = ""
        for _, item in enumerate(zip(*strs)):
            if len(set(item)) > 1:
                return prefix
            else:
                prefix += item[0]
        return prefix

本题以及其它leetcode题目代码github地址: github地址

混合云 idc机房托管最长公共子序列最长公共子串 php 数组最长数组字符串转数组

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38670.html

最长公共前缀（LCP）

摘要：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。思路先将字符串数组排序，在比较第一个字符串与最后一个字符串的公共前缀即可，只需比较第一个字符串与最后一个字符串保存公共前缀排序不一样则退出循环最长公共前缀 LCP(longest common prefix) Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀...

JasonZhang 2019-08-19 11:43 评论0 收藏0
＜LeetCode天梯＞Day023 最长公共前缀（切片法） | 初级算法 | Python

摘要：如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住...

kyanag 2021-11-12 10:36 评论0 收藏0
LeetCode14.最长公共前缀 JavaScript

摘要：最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。说明所有输入只包含小写字母。 LeetCode14.最长公共前缀 JavaScript 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例 1: 输入: [flower,flow,flight] 输出: fl...

wind5o 2019-08-23 14:51 评论0 收藏0
14. 最长公共前缀-----leetcode刷题（python解题）

摘要：题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。示例输入输出示例输入输出解释输入不存在公共前缀。 [TOC] 题目 **编写一个函数来查找字符串数组中的最长公共前缀。** 如果不存在公共前缀，返回空字符串。示例 1: 输入: [flower,flow,flight] 输出: fl 示例 2: 输入: [dog,racecar,car] 输出:...

Berwin 2019-07-31 10:38 评论0 收藏0
# Leetcode 14：Longest Common Prefix 最长公共前缀

摘要：公众号爱写编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。由于字符串长度不一，可以先遍历找出最小长度字符串，这里我选择抛错的形式，减少一次遍历。公众号：爱写bug Write a function to find the longest common prefix string amongst an array of strings. If there...

Keagan 2019-07-31 10:38 评论0 收藏0