LeetCode #205 Isomorphic Strings: วาฬ แมว ลิง นกแก้ว ประชันสมุดแปลงอักษร

LeetCode #205 Isomorphic Strings ให้สตริง s และ t ที่ยาวเท่ากัน เราต้องตัดสินว่าเปลี่ยนตัวอักษรแต่ละชนิดใน s ด้วยกฎเดิมตลอดทั้งคำแล้วได้ t หรือไม่ครับ ตัวต้นทางต่างกันต้องไม่แย่งตัวปลายทางเดียวกัน แต่จับคู่ตัวอักษรกับตัวมันเองได้ งานแบบนี้เจอในรหัสลับแทนตัวอักษร หรือการตรวจว่าสองตารางมีรูปแบบข้อมูลซ้ำตรงกันหรือเปล่า

s = "egg",  t = "add"  → true   (e → a, g → d)
s = "foo",  t = "bar"  → false  (o ต้องเป็นทั้ง a และ r)
s = "badc", t = "baba" → false  (a กับ c แย่ง a)

วันนี้ปลาวาฬสองสมุด แมวหนึ่งสมุดกับเซ็ต ลิงจำตำแหน่งแรก และนกแก้วนับจำนวนคู่ มาเถียงกันต่อหน้าบารอน สิงโตทะเลสวมเสื้อโค้ตผู้เป็นกรรมการครับ

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

ตัวละคร	วิธี	นิสัยที่เข้ากับวิธี
ปลาวาฬ “วาฬจดจ๋า”	สมุดสองเล่ม เก็บคู่ไปและกลับ	รอบคอบ ตรวจหลักฐานทั้งสองฝั่ง
แมว “เหมียวหวงช่อง”	สมุดหนึ่งเล่มกับเซ็ตปลายทางที่ถูกใช้	ประหยัดคำพูด แต่หวงที่นั่งไม่ให้ใครซ้ำ
ลิง “จ๋อจำแรก”	เทียบตำแหน่งที่แต่ละตัวปรากฏครั้งแรก	จำจุดเริ่มต้นเก่ง ชอบหารูปแบบ
นกแก้ว “แก้วคู่จิ๋ว”	นับตัวอักษรและคู่ที่ไม่ซ้ำ	พูดสั้น ชอบรวบทุกอย่างเป็นสูตรเดียว
บารอน สิงโตทะเลในเสื้อโค้ต	กรรมการ	อ่านกติกาก่อนตัดสิน และดูเวลาที่วัดจริง

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

โจทย์ใช้ ASCII ซึ่งมีชุดอักษรจำกัด พื้นที่ตามจำนวนชนิดจึงมีเพดานคงที่ แต่ผมใช้ O(k) ให้เห็นว่าเก็บอะไรจริง

วิธีที่ 1: ปลาวาฬสองสมุด — พจนานุกรมไปกลับ

วาฬจดจ๋ากางสมุดเล่มซ้ายว่า “จาก s ไป t เคยตกลงกันอย่างไร” แล้วกางเล่มขวาว่า “ตัวใน t มีเจ้าของฝั่ง s แล้วหรือยัง” เดินอ่านทีละตำแหน่ง ถ้ามีบันทึกเดิมที่ขัดกับคู่ปัจจุบันก็คืน False ทันที ถ้าไม่ขัดจึงจดทั้งสองทิศทาง

สมุดไปจับ foo→bar ได้ เพราะ o เปลี่ยนปลายทาง แต่ปล่อย badc→baba ผ่าน เพราะทุกตัวรักษาคู่เดิม ทั้งที่มีตัวต้นทางแย่งปลายทางกัน สมุดกลับจึงจำเป็นครับ

badc → baba
ไป:   b→b, a→a, d→b, c→a
กลับ: b→b แล้วพบ d→b   ← ปลายทาง b มีเจ้าของแล้ว!

d→b ผิด ส่วน b→b แทนตัวเองได้

เวลา: O(n) โดยเฉลี่ย และหยุดก่อนครบได้เมื่อเจอคู่ที่ผิด
หน่วยความจำเพิ่ม: O(k) สำหรับสองพจนานุกรม
ข้อดี: เห็นกติกาสองทิศทางตรง ๆ อธิบายบนกระดานง่าย และอ่านสาเหตุที่ไม่ผ่านได้ชัด
ข้อเสีย/edge cases: ทำงานกับสองสมุดทุกตำแหน่ง ต้องตรวจความขัดแย้งก่อนเขียนทับ มิฉะนั้นหลักฐานเดิมจะหาย

วิธีที่ 2: แมวหนึ่งสมุดกับเซ็ต — จองปลายทางครั้งเดียว

เหมียวหวงช่องพูดว่า “ฉันขอรู้แค่ว่าช่องนี้มีคนใช้แล้ว” แมวเก็บ mapping จากต้นทางไปปลายทาง แล้วแทนสมุดกลับด้วยเซ็ต used ของปลายทางที่ถูกจอง

ถ้าตัวต้นทางเคยเจอแล้ว แมวตรวจเพียงว่าปลายทางตรงกับที่จดไว้หรือไม่ ถ้าเป็นตัวต้นทางใหม่ จึงตรวจว่าปลายทางอยู่ใน used หรือยัง ถ้าอยู่ก็ไม่ผ่าน ถ้ายังว่างจึงบันทึกคู่และจองช่อง วิธีนี้ลดงานในรอบที่เจออักษรเดิมบ่อย ๆ ได้ครับ

จุดที่พลาดง่ายคือเช็ก b in used ทุกครั้งโดยไม่แยกตัวต้นทางใหม่กับเก่า คู่ g→d ที่เกิดซ้ำใน egg→add ต้องผ่าน เพราะเป็นเจ้าของเดิมกลับมา ไม่ใช่คนใหม่แย่งที่ แมวเลยตรวจความเป็นเจ้าของผ่านสมุดก่อนเสมอ

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

วิธีที่ 3: ลิงจำตำแหน่งแรก — เปรียบเทียบลายเซ็นของคำ

จ๋อจำแรกไม่สนใจชื่ออักษรเลย เขาเปลี่ยนแต่ละตำแหน่งเป็นหมายเลขตำแหน่งแรกที่เคยเห็นอักษรนั้น โดยเริ่มนับตำแหน่งจากศูนย์ เช่น paper กับ title ได้ลายเซ็นเดียวกัน ลายเซ็นในที่นี้คือลิสต์ที่บอกโครงสร้างการซ้ำ ไม่ใช่รหัสเข้ารหัสครับ

paper: p a p e r  →  [0, 1, 0, 3, 4]
title: t i t l e  →  [0, 1, 0, 3, 4]
ตำแหน่งที่ 2 ย้อนกลับไปหาอักษรเดียวกับตำแหน่งที่ 0 ทั้งคู่

ลายเซ็นเท่ากันแปลว่าตำแหน่งที่ซ้ำกันตรงกันทั้งสองคำ จึงรักษาทั้งคู่เดิมและการไม่รวมตัวต่างชนิด ลายเซ็นเก็บความสัมพันธ์แทนสมุดไปกลับครับ

ลิงรุ่นรีบเขียนใช้ [s.index(c) for c in s] เมธอด index เดินหาจากต้นคำเพื่อคืนตำแหน่งแรกของ c เมื่อเรียกใหม่ทุกตัวก็อาจเดินทับทางเดิมยาว ๆ หลายรอบ ลองคิดถึงคำที่ครึ่งแรกเป็น a และครึ่งหลังเป็น b ทุกครั้งที่หา b ต้องผ่านครึ่งแรกซ้ำ จึงเกิดเวลา O(n²) ได้แม้มีอักษรแค่สองชนิด

ลิงรุ่นจัดระเบียบจำตำแหน่งแรกใน dict แล้วเติมลิสต์จากค่าที่จำไว้ first_pattern จึงใช้เวลาเฉลี่ย O(n) โค้ดมีทั้งสองแบบครับ

เวลา: รุ่น index มีกรณีเลวร้าย O(n²) ส่วนรุ่นพจนานุกรมเป็น O(n) โดยเฉลี่ย
หน่วยความจำเพิ่ม: ทั้งคู่ O(n) เพราะสร้างลิสต์ลายเซ็นสองคำ รุ่นพจนานุกรมมีสมุด O(k) เพิ่มด้วย
ข้อดี: แยกการทำคำให้เป็นรูปแบบมาตรฐานออกมาใช้ซ้ำได้ เหมาะกับการอธิบายว่า “รูปแบบเดียวกัน” หมายถึงอะไร
ข้อเสีย/edge cases: สร้างลิสต์เต็มก่อนเทียบ จึงใช้พื้นที่ตามความยาวและไม่ได้หยุดทันทีที่พบคู่ผิดระหว่างสร้าง; รุ่น index สั้นแต่ซ่อนการค้นซ้ำ

วิธีที่ 4: นกแก้วนับจำนวนคู่ — เซ็ตสามกองกับสมการเดียว

แก้วคู่จิ๋วกระพือปีกแล้วประกาศ len(set(s)) == len(set(t)) == len(set(zip(s, t))) ฟังก์ชัน zip หยิบอักษรตำแหน่งตรงกันมาจับเป็นคู่ ส่วนเซ็ตทิ้งรายการที่ซ้ำกันไป นกแก้วจึงนับตัวต้นทางต่างชนิด ตัวปลายทางต่างชนิด และคู่ต่างชนิด แล้วขอให้จำนวนทั้งสามเท่ากัน

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

ab→aa นับได้สอง หนึ่ง และสอง จึงไม่ผ่าน ส่วนนับแค่อักษรสองฝั่งยังไม่พอ เช่น aab→abb มีสองชนิดเท่ากัน แต่มีสามคู่ จึงต้องนับคู่ด้วย

เวลา: O(n) โดยเฉลี่ย เดินผ่านข้อมูลเพื่อสร้างเซ็ตแต่ละกอง
หน่วยความจำเพิ่ม: O(min(n, k²)) ในกรณีทั่วไป เพราะคู่ที่ต่างกันอาจมากกว่าชนิดอักษร; เมื่อคำตอบผ่านเหลือ O(k)
ข้อดี: สั้น และใช้การสร้างเซ็ตของ Python มาช่วยทำงานซ้ำ ๆ เหมาะเมื่อทีมเข้าใจเหตุผลของสูตรร่วมกัน
ข้อเสีย/edge cases: อ่านสูตรครั้งแรกยาก มีต้นทุนสร้างคู่ และแม้คำจะผิดตั้งแต่ต้นก็อาจสร้างเซ็ตจากข้อมูลทั้งคำก่อนสรุป

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

ทุกฟังก์ชันคืนค่าจริงหรือเท็จ และเช็กความยาวก่อน เพราะ zip หยุดตามคำที่สั้นกว่า สตริงว่างสองคำให้ผ่านเพื่อรองรับการใช้นอกโจทย์ด้วย

บันทึกเป็น solution.py แล้วรัน python3 -I -B solution.py เทสต์มีตัวเดียว ตัวซ้ำ ช่องว่าง เครื่องหมาย และความยาวต่างกัน อีกชุดไล่คำจาก a,b ทุกแบบที่ยาวศูนย์ถึงสี่ ตรวจด้วยนิยามว่าอักษรตำแหน่งใด ๆ ซ้ำตรงกันทั้งสองฝั่ง จึงไม่ต้องอาศัยคำตอบจากวิธีใดเป็นตัวเฉลย

import unittest


def whale(s, t):
    if len(s) != len(t):
        return False
    forward, backward = {}, {}
    for a, b in zip(s, t):
        if a in forward and forward[a] != b:
            return False
        if b in backward and backward[b] != a:
            return False
        forward[a], backward[b] = b, a
    return True


def cat(s, t):
    if len(s) != len(t):
        return False
    mapping, used = {}, set()
    for a, b in zip(s, t):
        if a in mapping:
            if mapping[a] != b:
                return False
        else:
            if b in used:
                return False
            mapping[a] = b
            used.add(b)
    return True


def monkey_naive(s, t):
    return (len(s) == len(t)
            and [s.index(c) for c in s] == [t.index(c) for c in t])


def first_pattern(word):
    first = {}
    pattern = []
    for i, c in enumerate(word):
        if c not in first:
            first[c] = i
        pattern.append(first[c])
    return pattern


def monkey_dict(s, t):
    return len(s) == len(t) and first_pattern(s) == first_pattern(t)


def parrot(s, t):
    return (len(s) == len(t)
            and len(set(s)) == len(set(t)) == len(set(zip(s, t))))


ALL = [whale, cat, monkey_naive, monkey_dict, parrot]


class TestIsomorphic(unittest.TestCase):
    def test_examples_and_edges(self):
        cases = [
            ("egg", "add", True), ("foo", "bar", False),
            ("paper", "title", True), ("badc", "baba", False),
            ("ab", "aa", False), ("aa", "ab", False),
            ("", "", True), ("a", "z", True),
            ("aaaa", "bbbb", True), ("abcd", "abcd", True),
            ("a", "", False), ("", "a", False),
            ("a a", "b-b", True), ("12!1", "ab?a", 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_small_exhaustive(self):
        from itertools import product

        # Two positions are equal in s iff they are equal in t.
        for n in range(5):
            words = ["".join(p) for p in product("ab", repeat=n)]
            for s in words:
                for t in words:
                    expected = all(
                        (s[i] == s[j]) == (t[i] == t[j])
                        for i in range(n) for j in range(n)
                    )
                    for fn in ALL:
                        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 docs — timeit บน Python 3.14.7 จาก python3 -V สถาปัตยกรรม x86_64 จาก platform.machine() รันด้วย python3 -I -B ใช้เฉพาะโมดูลที่มากับ Python

ข้อมูลสองขนาดคือ n = 1,000 กับ 10,000 ทุกคู่แปลงกันได้จริงและมีอักษรต่างชนิดสิบหกตัว ผมสร้าง s จาก chr(65 + i * 16 // n) และ t จาก chr(97 + i * 16 // n) สำหรับ i ตั้งแต่ศูนย์ถึง n-1 ได้ช่วงอักษรซ้ำจาก A ถึง P และ a ถึง p ตำแหน่งแรกของอักษรช่วงท้ายจึงอยู่ไกล เห็นต้นทุนค้นซ้ำของลิงได้

สร้างข้อมูลนอกช่วงจับเวลา แล้วใช้ timeit.repeat(lambda: fn(s, t), number=100, repeat=5) กับแต่ละฟังก์ชัน เลือกเวลารวมที่น้อยที่สุดในห้ารอบ หารด้วยหนึ่งร้อยเพื่อได้เวลาต่อการเรียก แล้วคูณหนึ่งพันเป็นมิลลิวินาที ค่าด้านล่างปัดเป็นทศนิยมสามตำแหน่ง ตัวหนาคือค่าที่เร็วที่สุดต่อขนาด

วิธี / ฟังก์ชัน	n = 1,000 (ms/ครั้ง)	n = 10,000 (ms/ครั้ง)
ปลาวาฬ / `whale`	0.059	0.585
แมว / `cat`	0.029	0.275
ลิงค้นซ้ำ / `monkey_naive`	0.068	1.176
ลิงจำในสมุด / `monkey_dict`	0.067	0.692
นกแก้ว / `parrot`	0.034	0.324

แมวได้เปรียบบนข้อมูลนี้เพราะส่วนใหญ่เป็นอักษรที่เจอแล้ว จึงตรวจสมุดฝั่งเดียว ขณะที่วาฬยังตรวจและเขียนทั้งสองฝั่ง นกแก้วตามมาใกล้ ๆ ด้วยการสร้างเซ็ตผ่านกลไกของ Python ส่วนลิงแบบสมุดมีงานสร้างลิสต์สองชุด และลิงค้นซ้ำต้องไล่หาตัวที่เริ่มปรากฏไกลขึ้นเมื่อเพิ่มความยาว ตัวเลขนี้เป็นของเครื่องนี้และข้อมูลรูปแบบนี้เท่านั้น หากคำผิดตั้งแต่ช่วงต้น วิธีที่หยุดได้ทันทีอาจได้เปรียบมากขึ้น และชุดข้อมูลนี้ไม่ได้วัดหน่วยความจำ

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

สถานการณ์	เลือก	เหตุผล
สัมภาษณ์ไวท์บอร์ด	ปลาวาฬสองสมุด	อธิบายกติกาไปกลับได้ตรง และยกตัวอย่างหักล้างสมุดเดียวได้ง่าย
โค้ดงานจริงที่เป็น hot path (production)	เริ่มลองแมว แล้ววัดข้อมูลจริง	แมวเร็วที่สุดในชุดที่วัด แต่เส้นทางที่ถูกเรียกบ่อยต้องตัดสินด้วยภาระงานของระบบ
สอนมือใหม่	ปลาวาฬ แล้วค่อยแปลงเป็นแมว	เห็นหน้าที่ของสมุดกลับก่อนย่อให้เหลือเซ็ตจองปลายทาง
ต้องใช้ลายเซ็นไปจัดกลุ่มคำต่อ	ลิงแบบพจนานุกรม	ได้ลิสต์รูปแบบเก็บไว้ใช้งานต่อ โดยไม่ค้นจากต้นคำซ้ำ
อ่านข้อมูลเป็นคู่ทีละตัวแบบ streaming	แมวหรือปลาวาฬ	เก็บสถานะสะสมได้ แต่ต้องตรวจว่าทั้งสองฝั่งจบพร้อมกันด้วย
พื้นที่จำกัดและคำอาจผิด	แมวหรือปลาวาฬ	เก็บเฉพาะตัวอักษร ไม่ต้องสร้างลิสต์ยาวหรือสะสมคู่ที่ขัดกันจำนวนมาก

ค่าเริ่มต้นภายใต้กติกาของโจทย์: ผมเลือกปลาวาฬสองสมุดเพื่อความชัดเจนและเวลาเฉลี่ย O(n) ส่วนงานที่ต้องลดเวลาเรียกซ้ำจะลองแมวหนึ่งสมุดกับเซ็ตตามผลวัดนี้ก่อนครับ

บารอนสรุป

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

Recap

ลองเขียนคู่ของ badc→baba แล้วชี้ว่าปลายทางใดถูกแย่งก่อน
อธิบายให้ได้ว่าทำไมสมุดจากต้นทางไปปลายทางเพียงเล่มเดียวจึงยังไม่พอ
ไล่แมวด้วย egg→add แล้วแยกเจ้าของเดิมกลับมาออกจากเจ้าของใหม่แย่งช่อง
สร้างลายเซ็นของ paper และ title ด้วยมือ แล้วเทียบกับ first_pattern
พิสูจน์สูตรนกแก้วโดยแยกเหตุผลฝั่งต้นทางกับฝั่งปลายทาง
คัดลอกโค้ดไปรันเทสต์ แล้วเพิ่มกรณีที่ตัวเองเคยพลาด
เปลี่ยนข้อมูล benchmark ให้มีคู่ผิดตั้งแต่ต้น แล้ววัดใหม่ก่อนเลือกใช้ในงานจริง