LeetCode #242 Valid Anagram: ช้าง กระรอก ผึ้ง นกฮูก ใครนับแม่นสุด

LeetCode #242 Valid Anagram ให้เรารับสตริง s กับ t แล้วตอบว่าทั้งคู่ใช้ตัวอักษรชนิดเดียวกันและจำนวนเท่ากันไหม ตำแหน่งสลับกันได้ แต่ห้ามมีตัวไหนหายหรือเกิน ถ้าครบเงื่อนไขให้คืน True ไม่ครบให้คืน False ครับ

งานแบบนี้เจอได้ในเกมเรียงตัวอักษรใหม่ หรือการตรวจว่ารหัสสินค้าสองชุดมีตัวอักษรชุดเดียวกันโดยไม่สนลำดับ

s = "aab", t = "aba" → True
s = "aab", t = "abb" → False
s = "",    t = ""    → True

วันนี้ช้างเรียงแถว กระรอกนับลูกโอ๊ก ผึ้งรังผึ้ง 26 ช่อง และนกฮูกเช็คความยาวก่อน จะมาถกกัน โดยมี บารอน สิงโตทะเลสวมโค้ตเป็นกรรมการครับ

ผู้เข้าแข่งขัน

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
ช้างเรียงแถว ชื่อเล่น “น้องแถว”	เรียงทั้งสองฝั่งแล้วเทียบ	เจ้าระเบียบ ทุกตัวต้องยืนตามคิว
กระรอกนับลูกโอ๊ก ชื่อเล่น “จดจ๋อ”	นับด้วย `Counter`	ชอบทำบัญชีของสะสมให้ครบทุกชนิด
ผึ้งรังผึ้ง 26 ช่อง ชื่อเล่น “บัซน้อย”	อาร์เรย์นับความต่าง	รักช่องเก็บของที่มีตำแหน่งแน่นอน
นกฮูกเช็คความยาวก่อน ชื่อเล่น “ตาไว”	ตรวจความยาวแล้วใช้ `dict`	มองเงื่อนไขตัดสินก่อนลงแรง
บารอน สิงโตทะเลสวมโค้ต	กรรมการ	อ่านกติกา ดูผลทดลอง แล้วค่อยเคาะโต๊ะ

ให้ n เป็นความยาวของแต่ละสตริงในกรณีที่ยาวเท่ากัน และ k เป็นจำนวนตัวอักษรต่างชนิดที่ต้องเก็บ เวลาแบบ O(n) หมายถึงงานเพิ่มตามจำนวนตัวอักษรโดยคร่าว ๆ ไม่ใช่หน่วยวินาที ส่วนหน่วยความจำเพิ่มคือพื้นที่ทำงานที่ใช้เพิ่มจากอินพุตเดิมครับ

วิธีที่ 1: ช้างเรียงแถว — เรียงก่อนแล้วค่อยเทียบ

“ทุกตัวเข้าแถวตามตัวอักษรก่อน เดี๋ยวก็เห็นเอง!” น้องแถวพูดพลางจัดแถวด้วยงวง ถ้าสองคำมีตัวอักษรกับจำนวนตรงกัน เมื่อเรียงด้วยกฎเดียวกันก็ต้องได้รายการเดียวกัน การเรียงยังเก็บตัวซ้ำไว้ จึงไม่ทำข้อมูลจำนวนหายเหมือนการแปลงเป็นเซต

"aab" → [a, a, b]
"aba" → [a, a, b] → เท่ากัน
"abb" → [a, b, b] → ไม่เท่ากับแถวแรก

โค้ดเหลือเพียง sorted(s) == sorted(t) ฟังก์ชัน sorted สร้างลิสต์ใหม่ จึงไม่แก้สตริงต้นฉบับ การที่เขียนสั้นไม่ได้แปลว่าใช้พื้นที่น้อยนะครับ เพราะเราถือผลเรียงของทั้งสองฝั่งตอนเปรียบเทียบ

เวลา: O(n log n) ในกรณีทั่วไปที่ยาวเท่ากัน คือโตเร็วกว่าการอ่านครบหนึ่งรอบเพราะมีงานจัดลำดับเพิ่ม ถ้าความยาวต่างกัน ให้คิดงานเรียงของแต่ละฝั่งแยกกัน
หน่วยความจำเพิ่ม: O(n) สำหรับลิสต์ผลเรียงและพื้นที่ทำงาน
ข้อดี: อ่านง่าย เห็นเหตุผลว่าทำไมถูก และใช้กับตัวอักษร Unicode ได้ตามหน่วยที่ Python เก็บ
ข้อเสีย/edge cases: ยังเรียงก่อนแม้ความยาวไม่เท่ากัน สตริงว่างทั้งคู่ได้ลิสต์ว่างจึงเท่ากัน และการเทียบนี้สนตัวพิมพ์เล็กใหญ่กับเครื่องหมายทุกตัว

วิธีที่ 2: กระรอกนับลูกโอ๊ก — บัญชี Counter

จดจ๋อเปิดสมุดแล้วแย้งว่า “เราต้องการยอดแต่ละชนิด ทำไมต้องย้ายทุกตัวไปเข้าแถวด้วยล่ะ” Counter ในโมดูล collections เป็นเครื่องมือนับความถี่ เราส่งสตริงเข้าไปแล้วได้บัญชีว่าพบแต่ละตัวกี่ครั้ง ดูพฤติกรรมได้ใน เอกสาร Counter ของ Python

สำหรับ aab บัญชีคือ a มีสองตัว และ b มีหนึ่งตัว พอทำบัญชีของ aba ก็ได้ยอดเดียวกัน จึงเทียบ Counter(s) == Counter(t) ได้ทันที จุดสำคัญคือเราเทียบทั้งชื่อชนิดและยอดนับ ไม่ได้ดูแค่ว่ามีชนิดนั้นอยู่หรือเปล่า

เวลา: โดยเฉลี่ย O(n) อ่านสองสตริงเพื่อนับ แล้วเทียบบัญชีอีก O(k) ซึ่งไม่เกินขนาดข้อมูล
หน่วยความจำเพิ่ม: O(k) มีบัญชีของทั้งสองฝั่ง ถ้าจำกัดเฉพาะ a–z จำนวนชนิดไม่เกิน 26 จึงถือเป็นพื้นที่คงที่เมื่อวัดเทียบกับ n
ข้อดี: ตรงกับความหมายของโจทย์ โค้ดสั้น และรองรับตัวอักษรหลายภาษาโดยไม่ต้องกำหนดช่องล่วงหน้า
ข้อเสีย/edge cases: เวอร์ชันนี้สร้างบัญชีทั้งคู่แม้ความยาวต่างกัน และนับทุกสัญลักษณ์ที่รับมา ไม่ตัดช่องว่างหรือเปลี่ยนตัวพิมพ์ให้เอง

คำว่า Unicode ต้องระวังนิดหนึ่งครับ Python เดินสตริงตาม code point หรือรหัสของส่วนประกอบข้อความ ไม่ใช่ตามตัวที่ตามองเห็นเสมอไป เช่น กิข กับ ขกิ มีองค์ประกอบ ก, ิ, ข เหมือนกัน จึงผ่าน แม้ตำแหน่งสระอาจทำให้หน้าตาข้อความต่างไป ส่วน กิ กับ กี ไม่ผ่านเพราะเป็นคนละสระ

อีกกรณีในเทสต์คือ \u00e9 กับ e\u0301 ซึ่งอาจแสดงเป็น é คล้ายกัน แต่ฝั่งแรกเป็นรหัสเดียว ส่วนอีกฝั่งเป็น e ตามด้วยเครื่องหมายเน้นเสียง จดจ๋อจะตอบ False เพราะรหัสไม่ตรงกัน ถ้าผลิตภัณฑ์ต้องการเทียบตามรูปที่ผู้ใช้อ่าน ต้องตกลงกฎจัดรูปข้อความก่อนนับ บทความนี้เทียบรหัสตามอินพุตตรง ๆ ครับ

วิธีที่ 3: ผึ้งรังผึ้ง 26 ช่อง — บวกและลบในรอบเดียว

บัซน้อยชูรังที่ติดป้าย a ถึง z แล้วบอกว่า “ถ้ากติกามีแค่อักษรอังกฤษตัวเล็ก ผมจองช่องไว้เลย!” อาร์เรย์ในที่นี้ใช้ลิสต์ของ Python เป็นแถวช่องนับ ตัว a อยู่ช่องแรก และ z อยู่ช่องสุดท้าย ใช้ ord(char) - ord("a") เปลี่ยนตัวอักษรเป็นตำแหน่งช่อง

อ่านคู่ตัวอักษรจาก s และ t ด้วย zip ในรอบเดียว เจอตัวจาก s บวกหนึ่ง เจอตัวจาก t ลบหนึ่ง หลังจบทุกช่องต้องเป็นศูนย์ เพราะแต่ละชนิดที่เข้ามาต้องถูกหักออกครบ

s = "ab", t = "ba"      ช่อง a   ช่อง b
เริ่มต้น                    0       0
คู่แรก: +a, -b             1      -1
คู่สอง: +b, -a             0       0 → True

ค่าติดลบระหว่างทางยังไม่ใช่คำตอบว่าไม่ผ่านนะครับ ในภาพช่อง b ติดลบก่อนแล้วกลับมาศูนย์ได้ อีกจุดที่ขาดไม่ได้คือตรวจความยาวก่อนใช้ zip เพราะมันหยุดเมื่อฝั่งสั้นหมด ถ้าไม่ตรวจ ตัวส่วนเกินอาจไม่ถูกอ่าน

เวลา: O(n) อ่านคู่ตัวอักษรครบหนึ่งรอบ แล้วตรวจช่องนับจำนวนคงที่
หน่วยความจำเพิ่ม: O(1) หรือพื้นที่คงที่ เพราะมีช่องนับ 26 ช่องไม่ว่าคำจะยาวขึ้นแค่ไหน ภายใต้แบบจำลองนับช่องเก็บค่าที่ใช้ทั่วไปในโจทย์นี้
ข้อดี: ขอบเขตพื้นที่ชัดเจน เก็บเพียงยอดต่าง และไม่ต้องสร้างบัญชีแยกสองชุด
ข้อเสีย/edge cases: ใช้เฉพาะ a–z ตามสัญญาของฟังก์ชันนี้ ตัวไทย ตัวพิมพ์ใหญ่ หรือสัญลักษณ์อื่นอาจทำให้ดัชนีผิดหรือเกิดข้อผิดพลาดได้ จึงไม่ควรส่งเข้ามาโดยไม่เปลี่ยนวิธี

แม้เป็นพื้นที่คงที่ บัซน้อยก็ไม่ได้แก้ข้อมูลเดิมหรือทำงานโดยไม่มีพื้นที่ช่วยเลย ถ้านับขนาดจำนวนเต็มละเอียดถึงระดับบิต ยอดที่โตขึ้นก็ต้องใช้บิตเพิ่มได้ แต่การวิเคราะห์มาตรฐานของข้อนี้นับจำนวนช่องเป็นหลัก

วิธีที่ 4: นกฮูกเช็คความยาวก่อน — dict และทางออกเร็ว

ตาไวขยับแว่น “ถ้าความยาวไม่เท่ากัน ก็ไม่ต้องเปิดสมุดเลยครับ” เมื่อยาวเท่ากันจึงสร้าง dict หรือพจนานุกรมจับคู่ตัวอักษรกับยอดคงเหลือจาก s โครงสร้างนี้ใช้การแฮช คือคำนวณตำแหน่งค้นหาจากคีย์ ทำให้เพิ่มและค้นค่าได้เร็วโดยเฉลี่ย

จากนั้นอ่าน t เพื่อตัดยอดทีละตัว ถ้าไม่มียอดให้ตัดก็ตอบ False ได้เลย ถ้ายอดเหลือหนึ่งแล้วถูกใช้ก็ลบคีย์นั้นออก สุดท้ายพจนานุกรมต้องว่าง เพราะทุกตัวถูกใช้ครบ วิธีนี้ต่างจากผึ้งที่เก็บยอดสุทธิ: ตาไวเก็บของฝั่งแรกให้ครบก่อน จึงรู้ว่าของชิ้นไหนไม่มีเหลือจริง ๆ

เวลา: โดยเฉลี่ย O(n) เมื่ออ่านครบ ถ้าความยาวต่างกันคืนคำตอบได้ใน O(1) เพราะ len ของสตริง Python อ่านความยาวที่เก็บไว้ได้เลย
หน่วยความจำเพิ่ม: O(k) สำหรับบัญชีฝั่งเดียว ภายใต้กติกา a–z ก็มีจำนวนคีย์จำกัดเช่นกัน
ข้อดี: คุมจังหวะหยุดได้เอง ไม่ต้องอ่าน t ต่อหลังพบตัวที่ใช้เกิน และรองรับ Unicode แบบ code point เช่นเดียวกับกระรอก
ข้อเสีย/edge cases: โค้ดยาวกว่าและมีเงื่อนไขในลูป ต้องเก็บ s ครบก่อนจึงเริ่มตัดยอด สตริงว่างทั้งคู่ผ่านเพราะบัญชีว่างตั้งแต่ต้น

การออกเร็วช่วยมากหรือน้อยขึ้นกับข้อมูล ถ้าเป็น anagram จริงก็ต้องตรวจจนหมด ถ้าพบตัวที่ผิดท้ายคำ ก็ประหยัดไปเพียงนิดเดียว จึงยังสรุปไม่ได้ว่าตาไวจะเร็วกว่าเพื่อนเพียงเพราะมีคำว่า “เช็คก่อน” ครับ

โค้ดทุกวิธี พร้อมเทสต์

คัดลอกบล็อกนี้เป็นไฟล์แล้วรันด้วย python3 -I -B file.py ได้เลย ผมรันผ่านแล้วบนเครื่องนี้ เทสต์หลักให้ทุกวิธีเจอคำปกติ คำว่าง ตัวเดียว ความยาวต่าง ตัวซ้ำ และตัวขอบช่วง a, z ส่วนเทสต์ Unicode ใช้เฉพาะสามวิธีที่รับข้อมูลชนิดนั้นตามสัญญา

from collections import Counter
import unittest


def elephant(s, t):
    return sorted(s) == sorted(t)


def squirrel(s, t):
    return Counter(s) == Counter(t)


def bee(s, t):
    # Contract: both strings contain only lowercase English a-z.
    if len(s) != len(t):
        return False
    counts = [0] * 26
    base = ord("a")
    for left, right in zip(s, t):
        counts[ord(left) - base] += 1
        counts[ord(right) - base] -= 1
    return all(value == 0 for value in counts)


def owl(s, t):
    if len(s) != len(t):
        return False
    counts = {}
    for char in s:
        counts[char] = counts.get(char, 0) + 1
    for char in t:
        remaining = counts.get(char, 0)
        if remaining == 0:
            return False
        if remaining == 1:
            del counts[char]
        else:
            counts[char] = remaining - 1
    return not counts


ALL = [elephant, squirrel, bee, owl]


class TestAnagram(unittest.TestCase):
    def test_lowercase(self):
        cases = [
            ("anagram", "nagaram", True),
            ("rat", "car", False),
            ("", "", True),
            ("", "a", False),
            ("a", "a", True),
            ("a", "b", False),
            ("ab", "a", False),
            ("aab", "abb", False),
            ("aaaa", "aaaa", True),
            ("abc", "cba", True),
            ("az", "za", True),
        ]
        for fn in ALL:
            for s, t, expected in cases:
                with self.subTest(fn=fn.__name__, s=s, t=t):
                    self.assertEqual(fn(s, t), expected)

    def test_unicode_code_points(self):
        # bee has a narrower a-z contract, so it is excluded here.
        for fn in (elephant, squirrel, owl):
            for s, t, expected in [
                ("กิข", "ขกิ", True),
                ("กิ", "กี", False),
                ("\u00e9", "e\u0301", False),
            ]:
                with self.subTest(fn=fn.__name__, s=s, t=t):
                    self.assertEqual(fn(s, t), expected)


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

Benchmark ที่รันจริง (23 ต.ค. 2026 บนเครื่องนี้)

ใช้ Python 3.14.7 จาก python3 -V และสถาปัตยกรรม x86_64 จาก platform.machine() จับเวลาด้วย timeit ของ Python โดยสร้าง s จากตัวเล็กอังกฤษที่สุ่มด้วย random.Random(242) แล้วสับลำดับสำเนาให้เป็น t ทั้งสองขนาดจึงเป็นกรณีตอบ True ทุกวิธีต้องอ่านข้อมูลครบ

เตรียมข้อมูลนอกช่วงจับเวลา ใช้ชุดเดียวกันให้ทุกวิธีในแต่ละขนาด และตรวจคำตอบก่อนวัด ขนาด 1,000 ตัวรัน 200 ครั้งต่อชุด ขนาด 100,000 ตัวรัน 5 ครั้งต่อชุด ทำซ้ำขนาดละ 5 ชุดด้วย timeit.repeat แล้วเลือกเวลารวมต่ำสุดหารจำนวนครั้ง จึงเป็น best of 5 ต่อการเรียกหนึ่งครั้ง ไม่ใช่เวลาเฉลี่ยทั้งห้าชุด

วิธี	n = 1,000 (มิลลิวินาที/ครั้ง)	n = 100,000 (มิลลิวินาที/ครั้ง)
ช้าง: sorted	0.153	20.066
กระรอก: Counter	0.040	4.307
ผึ้ง: ช่องนับ 26 ช่อง	0.059	7.262
นกฮูก: ตรวจความยาว + dict	0.070	8.269

กระรอกเร็วที่สุดทั้งสองขนาด ซึ่งสอดคล้องกับการที่ Python รุ่นนี้มีตัวช่วยนับภายในที่ทำงานระดับ C จึงลดงานวนทีละตัวในโค้ด Python ที่เราเขียนเอง ผึ้งกับนกฮูกยังวนและอัปเดตยอดใน Python โดยนกฮูกมีการค้นหาและเงื่อนไขจัดการคีย์เพิ่ม ส่วนช้างต้องจัดลำดับจึงมีงานเพิ่มเมื่อข้อมูลยาวขึ้น นี่เป็นคำอธิบายจากโครงสร้างโค้ดประกอบผลเวลา ไม่ใช่ผลการวัดแยกต้นทุนแต่ละคำสั่ง และชุดนี้ไม่ได้วัดประโยชน์การออกเร็วเมื่อข้อมูลผิดครับ ตัวเลขนี้ใช้กับเครื่องนี้และข้อมูลชุดนี้เท่านั้น รวมทั้งไม่ได้วัดหน่วยความจำจริง จึงไม่ควรใช้เวลามาตัดสินพื้นที่ที่แต่ละวิธีใช้

ตารางเลือกวิธีตามสถานการณ์

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	ผึ้ง	อธิบายยอดต่างและพื้นที่คงที่ได้ชัด เมื่อยืนยันว่าอินพุตมีแค่ `a–z`
โค้ดงานจริงที่เป็น hot path (production)	กระรอกเป็นจุดเริ่มต้น	hot path คือส่วนที่ถูกเรียกบ่อยมาก ชุดทดลองนี้ Counter เร็วสุด แล้วค่อยวัดซ้ำด้วยข้อมูลใช้งานจริง
สอนมือใหม่	ช้าง แล้วต่อด้วยกระรอก	แถวที่เรียงแล้วเห็นภาพง่าย ก่อนเปลี่ยนมาคิดเรื่องยอดนับ
ต้องการพื้นที่ทำงานที่ขอบเขตชัด ภายใต้ `a–z`	ผึ้ง	มีช่องนับตายตัว แต่ควรรู้ว่า Counter และ dict ก็มีจำนวนคีย์จำกัดภายใต้กติกาเดียวกัน
พบความยาวต่างกันบ่อย	นกฮูก	คืนคำตอบก่อนสร้างบัญชี และยังตัดจบเมื่อพบตัวที่ไม่เหลือให้ใช้
ข้อความไทยหรือ Unicode	กระรอก	รองรับคีย์หลากหลาย แต่ต้องตกลงว่าจะเทียบ code point หรือรูปข้อความก่อน

ค่าเริ่มต้นภายใต้กติกาของโจทย์: ผมเลือก Counter(s) == Counter(t) เพราะอ่านตรงเจตนาและเร็วที่สุดในการทดลองนี้ ถ้าโจทย์สัมภาษณ์ต้องการแสดงการนับเองหรือจำกัดช่องเก็บให้แน่นอน ค่อยหยิบวิธีผึ้งออกมาอธิบายครับ

บารอนสรุป

บารอนดึงปกโค้ตแล้วเคาะโต๊ะ “รอบนี้กระรอกจดจ๋อชนะด้านเวลา ทั้งคำสั้นและคำยาวที่เราทดลองครับ” ผึ้งบัซน้อยยังได้คะแนนเรื่องรังขนาดแน่นอน แต่คำว่า O(n) ไม่ได้ทำให้ลูปทุกแบบเร็วเท่ากัน ช้างน้องแถวเหมาะกับการเริ่มอธิบาย ส่วนนกฮูกตาไวมีทางลัดเมื่อข้อมูลไม่ผ่าน ซึ่งสนามวันนี้ยังไม่ได้วัด ถ้าเปลี่ยนเป็นข้อความไทย ให้เลือกวิธีที่รับ Unicode และตกลงความหมายของตัวอักษรให้ชัดก่อนส่งขึ้นโต๊ะกรรมการ

Recap

ลองนับ aab กับ abb ด้วยมือ แล้วอธิบายว่าทำไมดูแค่ชนิดตัวอักษรไม่พอ
วาดช่อง a และ b แล้วเดินตามลูปผึ้งจนยอดกลับเป็นศูนย์
คัดลอกโค้ดไปรันเทสต์ และเพิ่มกรณีตัวซ้ำที่จำนวนไม่ตรงอีกหนึ่งคู่
ชี้ตำแหน่งตรวจความยาวก่อน zip และอธิบายว่าป้องกันอะไร
ลองเทียบคำไทยที่มีสระ แล้วแยกสิ่งที่ตามองเห็นออกจาก code point
วัด Counter กับวิธีที่สนใจบนข้อมูลของตัวเอง โดยเตรียมอินพุตนอกช่วงจับเวลา