1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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.

# 来源:力扣(LeetCode)
# 链接:https: // leetcode-cn.com/problems/longest-common-prefix

class Solution:
def longestCommonPrefix(self, strs) -> str:
if not strs:
return ''
r = []
for item in zip(*strs): # 将 str 转换为二维矩阵式,遍历每个单元
# 若二维矩阵式每一项用 set 方式去重,三个都为重复的话,长度将为 1,此时 str 中每个元素该位置的值相同,将 true 添加到结果集合中
r.append(len(set(item)) == 1)
# 用于解决全部字符串相等时的情况,在后面加个 0,可以截取整个数组
r += [0]
# r.index(0) 表示相同字符串的截取位置,res 则为最长公共前缀
res = strs[0][:r.index(0)]
return res

def __init__(self, arr):
for item in ex:
print(self.longestCommonPrefix(item))

ex = [["dog", "racecar", "car"], ["flower", "flow", "flight"], []]
Solution(ex)

这道题用到了 python 的一个独有的数据处理能力,把数组转置为矩阵,通过判断矩阵每行的重复数为 1,判别数组中的每个元素的公共前缀。有点曲径通幽处的感觉,很妙。题解是我看了一个老哥的解答之后优化的,那老哥直接用了生成器,两行搞定了,可能理解上需要花点时间,我就按照自己的理解写成了一般式了。