Chương trình tìm tiền tố chung dài nhất từ ​​danh sách các chuỗi trong Python

Giả sử chúng ta có một danh sách các chuỗi chữ thường, chúng ta phải tìm tiền tố chung dài nhất.

Vì vậy, nếu đầu vào là ["antivirus", "ngược chiều kim đồng hồ", "antigravity"], thì đầu ra sẽ là "chống"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

sắp xếp các từ trong danh sách theo thứ tự bảng chữ cái

• prefix:=một danh sách mới
• cờ:=0
• đối với tôi trong phạm vi từ 0 đến kích thước của từ [0], hãy thực hiện
  • đối với mỗi j trong từ, hãy thực hiện
    • nếu j [i] không giống với phần tử cuối cùng của tiền tố, thì
      • xóa phần tử cuối cùng khỏi tiền tố
      • cờ:=1
      • ra khỏi vòng lặp
  • nếu cờ giống 1, thì
    • ra khỏi vòng lặp
• trả về chuỗi sau khi nối tất cả các phần tử có trong mảng tiền tố

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

anti