LeetCode #49 Group Anagrams: จัดกลุ่มคำที่ตัวอักษรเหมือนกัน

โจทย์ให้ลิสต์สตริง แล้วคืนกลุ่มของคำที่เป็น anagram กัน (ใช้ตัวอักษรชุดเดียวกันแค่สลับที่) ตามLeetCode 49

หัวใจคือหา ลายนิ้วมือ ของแต่ละคำ แล้วโยนเข้าแมป

วิธีที่ 1: เรียงตัวอักษรเป็นคีย์ — ค่าเริ่มต้นที่อ่านง่าย

เรียงอักขระในคำ ได้สตริงคีย์เดียวกันสำหรับ anagram เวลาประมาณ O(n * k log k) เมื่อ k คือความยาวคำ

วิธีที่ 2: นับความถี่ 26 ตัวเป็นคีย์

นับ a–z แล้วใช้ tuple ของนับเป็นคีย์ เวลา O(n * k) เหมาะเมื่อตัวอักษรเป็น English lowercase ตามข้อจำกัดโจทย์

วิธีที่ 3: sorted + defaultdict แบบสั้น

แนวเดียวกับวิธี 1 แต่เขียนกระชับด้วย defaultdict(list) อ่านง่ายในโค้ดสัมภาษณ์

import unittest
from collections import defaultdict

def group_sorted(strs):
    buckets = defaultdict(list)
    for s in strs:
        buckets["".join(sorted(s))].append(s)
    return list(buckets.values())

def group_count(strs):
    buckets = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - 97] += 1
        buckets[tuple(count)].append(s)
    return list(buckets.values())

def normalize(groups):
    return sorted(sorted(g) for g in groups)

class GroupAnagramsTests(unittest.TestCase):
    def test_examples(self):
        cases = [
            (["eat", "tea", "tan", "ate", "nat", "bat"], [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]),
            ([""], [[""]]),
            (["a"], [["a"]]),
        ]
        for words, expected in cases:
            for method in (group_sorted, group_count):
                with self.subTest(method=method.__name__, words=words):
                    self.assertEqual(normalize(method(words)), normalize(expected))

if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	sorted key	count tuple
อ่านง่ายสัมภาษณ์	ดี	ดีถ้าอธิบาย count
k ยาวมาก	ช้ากว่า (log k)	ดีกว่า
ตัวอักษรไม่จำกัด a–z	ใช้ได้	ต้องปรับขนาดอักขระ
หน่วยความจำ	เก็บสตริงคีย์	เก็บ tuple 26 ช่อง

ค่าเริ่มต้นที่ผมใช้: sorted key ถ้า n ไม่ใหญ่ และข้อจำกัดเป็นสตริงทั่วไป — ใช้ count เมื่อโจทย์ยืนยัน lowercase และอยากได้ O(n*k)

Recap

• หาคีย์ร่วมของ anagram แล้วจัดกลุ่มในแมป
• sorted = อ่านง่าย, count = เส้นตรงเมื่อจำกัดอักขระ
• อย่าลืมเคสสตริงว่างและคำเดียว
• เทสต์ด้วยการ normalize ลำดับกลุ่มก่อนเทียบ