โปรแกรมนับวิธีการต่อคำให้เป็นพาลินโดรมใน Python

ได้รับลิสต์คำที่ ไม่ซ้ำกัน หาจำนวนวิธี นำคำสองคำต่างกันมาต่อกัน (เรียงลำดับสำคัญ) ให้ได้ พาลินโดรม

ตัวอย่าง

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

Output: 3

คู่ที่เป็นพาลินโดรม: "time"+"emit"="timeemit", "emit"+"time"="emittime", "mo"+"m"="mom"

แนวทางแก้ปัญหา

Brute Force O(N² × L) (N = จำนวนคำ, L = ความยาวเฉลี่ย):

• ลองทุกคู่ (i, j) ที่ i != j
• เช็ค words[i] + words[j] เป็นพาลินโดรมหรือไม่

โค้ดต้นฉบับทำลูป 2 รอบ (รอบที่ 2 reverse words) ซึ่งซับซ้อนเกินไป - ทำ single loop ได้

การใช้งาน (Python - ปรับปรุง)

class Solution:
    def solve(self, words):
        def is_palindrome(s):
            return s == s[::-1]
        
        count = 0
        n = len(words)
        
        for i in range(n):
            for j in range(n):
                if i != j and is_palindrome(words[i] + words[j]):
                    count += 1
        
        return count

# ทดสอบ
ob = Solution()
print(ob.solve(["time", "emit", "mo", "m"]))  # Output: 3

วิธีที่เร็วกว่า: Hash Map O(N × L)

class Solution:
    def solve(self, words):
        word_set = {w: i for i, w in enumerate(words)}
        count = 0
        
        for i, w in enumerate(words):
            rev = w[::-1]
            # Case 1: w + rev(w) (ต้องเป็นคำคนละตัว)
            if rev in word_set and word_set[rev] != i:
                count += 1
            
            # Case 2: split w = left + right, left palindrome, rev(right) in dict
            # Case 3: split w = left + right, right palindrome, rev(left) in dict
            # (implementation omitted for brevity)
        
        return count

ความซับซ้อน

• Brute Force: O(N² × L)
• Optimized: O(N × L²) หรือ O(N × L) กับ Trie