ค้นหาและแทนที่รูปแบบ (Find and Replace Pattern) ใน Python

โจทย์: กำหนดลิสต์คำ words และรูปแบบ pattern หาคำที่ match pattern โดยมีการแปลงตัวอักษรแบบ bijection (1-1 mapping)

ตัวอย่าง

words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee", "aqq"] (mee: m→a, e→b; aqq: a→a, q→b)
"ccc" ไม่ match เพราะ c→a และ c→b ขัดแย้งกัน

อัลกอริทึม: Normalization Pattern

แปลงทั้ง word และ pattern ให้เป็น "รูปแบบมาตรฐาน" เช่น ใช้ตัวเลขแทนลำดับการปรากฏตัวอักษรใหม่

• "abb" → "0 1 1"
• "mee" → "0 1 1" ✓
• "ccc" → "0 0 0" ✗

ตัวอย่างโค้ด Python

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        def normalize(word):
            """แปลงคำเป็นรูปแบบตัวเลขตามลำดับการปรากฏ"""
            mapping = {}
            result = []
            next_id = 0
            for ch in word:
                if ch not in mapping:
                    mapping[ch] = next_id
                    next_id += 1
                result.append(str(mapping[ch]))
            return " ".join(result)
        
        pattern_norm = normalize(pattern)
        return [word for word in words if normalize(word) == pattern_norm]

# ทดสอบ
ob = Solution()
print(ob.findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"], "abb"))
# Output: ['mee', 'aqq']

ตัวอย่าง Input/Output

Input: ["abc","deq","mee","aqq","dkd","ccc"] "abb"
Output: ['mee', 'aqq']

ความซับซ้อน: Time O(n×m) где n=จำนวนคำ, m=ความยาวคำ