Chương trình đếm số cách nối 2 từ khác nhau thành palindrome trong Python

Cho danh sách từ distinct. Đếm số cặp từ khác nhau (thứ tự quan trọng) mà nối lại thành palindrome.

Ví dụ: ["time", "emit", "mo", "m"] → 3 ("timeemit", "emittime", "mom").

Giải thuật (Kiểm tra tất cả cặp - O(n^2 * L))

1. Hàm is_palindrome(w1, w2) kiểm tra w1+w2 == reverse(w1+w2).
2. Duyệt 2 lần: lần 1 thứ tự gốc, lần 2 đảo ngược mảng (để đếm cả (i,j) và (j,i)).
3. Với mỗi cặp i < j: nếu nối thành palindrome → res++.

Có thể tối ưu bằng Trie hoặc hashmap prefix/suffix cho n lớn.

Ví dụ minh họa

class Solution:
    def solve(self, words):
        def is_palindrome(w1, w2):
            w3 = w1 + w2
            return w3 == w3[::-1]
        
        res = 0
        ln = len(words)
        for _ in range(2):
            for i in range(ln):
                for j in range(i + 1, ln):
                    res += is_palindrome(words[i], words[j])
            words = words[::-1]
        return res

ob = Solution()
words = ["time", "emit", "mo", "m"]
print(ob.solve(words))  # Output: 3

Đầu vào / Đầu ra

Input: ["time", "emit", "mo", "m"]

Output: 3