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

Cho danh sách chuỗi chữ thường, tìm tiền tố chung dài nhất.

Ví dụ

Đầu vào: ["antivirus", "anticlockwise", "antigravity"].
Đầu ra: "anti".

Thuật toán

1. Sắp xếp danh sách theo thứ tự từ điển.
2. Duyệt từng ký tự của chuỗi đầu tiên (sau khi sắp xếp): thêm vào prefix.
3. Kiểm tra tất cả chuỗi có ký tự tại vị trí đó giống với ký tự vừa thêm không. Nếu không, xóa ký tự đó và dừng.
4. Trả về chuỗi ghép từ prefix.

Mã nguồn Python

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 / Đầu ra

Input: ["antivirus", "anticlockwise", "antigravity"]
Output: anti