Python 中从字符串列表查找最长公共前缀的程序

假设我们有一个小写字符串列表，我们需要找到最长的公共前缀。

因此，如果输入类似于 ["antivirus", "anticlockwise", "antigravity"]，则输出将为 "anti"

为了解决这个问题，我们将遵循以下步骤 -

按字母顺序对列表 words 进行排序

  • prefix := 一个新的列表
  • flag := 0
  • 对于 i 的范围从 0 到 words[0] 的大小，执行
    • 对于 words 中的每个 j，执行
      • 如果 j[i] 与 prefix 的最后一个元素不同，则
        • 从 prefix 中删除最后一个元素
        • flag := 1
        • 退出循环
    • 如果 flag 等于 1，则
      • 退出循环
  • 返回连接 prefix 数组中所有元素后的字符串

让我们看看以下实现以获得更好的理解 -

示例

 实时演示

class Solution:
   def solve(self, words):
      words.sort()
      prefix = []
      flag = 0
      for i in range(len(words[0])):
         prefix.append(words[0][i])
         for j in words:
            if j[i] != prefix[-1]:
               prefix.pop()
               flag = 1
               break
         if flag == 1:
            break
         return ''.join(prefix)
ob = Solution()
words = ["antivirus", "anticlockwise", "antigravity"]
print(ob.solve(words))

输入

["antivirus", "anticlockwise", "antigravity"]

输出

anti

更新于: 2020年10月6日

2K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告