字符串數組最長公共前綴

mrli2016 發布于2019-07-25 12:04 / 2940人閱讀

摘要：字符串數組最長公共前綴給出字符串數組，查找這個數組中所有字符串的最長公共前綴思路從開始自增，判斷每個字符串位置的字符是否一致，不一致則之前的串為最長公共字符串。利用函數的特點返回可迭代的對象，只要判斷長度大于，則表明此元素非公共字符。

字符串數組最長公共前綴 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地址

GPU云服務器云服務器最長公共子序列最長公共子串 php 數組最長數組字符串轉數組

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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