On this page

ข้อ 57 · LC17 Letter Combinations of a Phone Number (ตัวอักษรจากเบอร์โทร) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

map (แปลง) ตัวเลขบนแป้นโทรศัพท์เป็นทุก combination ของตัวอักษรที่กดได้ ด้วย backtracking ทีละ digit

โจทย์ (LC17): กำหนด string (สตริง) ที่ประกอบด้วย digit (หลักตัวเลข) ตั้งแต่ 2 ถึง 9 มา ให้ return ทุก letter combination ที่เป็นไปได้ที่ตัวเลขนั้นอาจหมายถึง (เรียงลำดับคำตอบแบบใดก็ได้) โดย mapping ของแต่ละ digit ไปตัวอักษรเป็นแบบเดียวกับปุ่มโทรศัพท์: 2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, 9=wxyz (เลข 1 ไม่มีตัวอักษรกำกับ)

Example 1

Input:: digits = "23"
Output:: ['ad','ae','af','bd','be','bf','cd','ce','cf']
Explanation:: เลข 2 ให้ a/b/c เลข 3 ให้ d/e/f จับคู่กันครบทุกแบบ

Example 2

Input:: digits = "2"
Output:: ['a','b','c']

Example 3

Input:: digits = ""
Output:: []
Explanation:: สตริงว่าง ไม่มีอะไรให้กดเลย

Constraints (ข้อจำกัด)

0 <= digits.length <= 4
digits[i] เป็นตัวเลข 2 ถึง 9

แนวทาง — ต้องใช้อะไร & คิดยังไง

โจทย์นี้คือ backtracking แบบตรงแบบ เพราะเราต้อง build คำตอบทีละตัวอักษร และแต่ละ digit มีหลาย choice (2-4 ตัว) จึงเข้ารูป choose → explore → unchoose ที่เรียนในหน้า intro พอดี สิ่งที่ต้องมีคือ mapping (hash map) จาก digit ไปตัวอักษรบนปุ่มนั้น

ถ้าคิดแบบตรง ๆ เราอาจอยาก loop (วน) for ซ้อนกันหนึ่งชั้นต่อหนึ่ง digit แต่ทำแบบนั้นไม่ได้เพราะจำนวน digit ไม่คงที่ (digits ยาวเท่าไหร่ก็ได้) recursion จึงเข้ามาแทนการซ้อน for ให้เรา: depth (ความลึก) ของ recursion เท่ากับจำนวน digit โดยอัตโนมัติ

สร้าง mapping digit → ตัวอักษร และ initialize (ตั้งค่าเริ่มต้น) array (ลิสต์) result กับ path (ตัวอักษรที่ choose ไว้แล้ว)
เขียนฟังก์ชัน backtrack(i) โดย i คือ index (ตำแหน่ง) ของ digit ที่กำลัง choose อยู่
ถ้า i เท่ากับ length (ความยาว) ของ digits แปลว่า choose ครบทุก digit แล้ว join (ต่อ) path เป็น string เก็บลง result แล้ว return
ไม่งั้น iterate (วน) ตัวอักษรทุกตัวบนปุ่มของ digits[i]: choose (append ลง path) → explore (เรียก backtrack(i+1)) → unchoose (pop ออก)
อย่าลืมดักกรณี digits ว่างตั้งแต่ต้น ให้ return [] เลย

จุดพลาดที่พบบ่อย

ถ้าไม่ดักกรณี digits ว่างไว้ก่อน ฟังก์ชันจะ return [''] (array ที่มี string ว่างหนึ่งตัว) แทนที่จะเป็น [] เพราะ backtrack(0) จะมองว่า choose ครบทันที อีกจุดคือลืม path.pop() ทำให้ตัวอักษรค้างสะสมข้าม branch

ไล่ทีละสเต็ป

ลองไล่ digits = "23" ดูค่า path ตอน enter และ exit แต่ละชั้นของ recursion:

i	action	path	result หลังทำ
0	choose 'a'	['a']	-
1	choose 'd' → i=2 ครบ	['a','d']	['ad']
1	unchoose 'd', choose 'e' → ครบ	['a','e']	['ad','ae']
1	unchoose 'e', choose 'f' → ครบ	['a','f']	['ad','ae','af']
0	unchoose 'a', choose 'b' ...	['b']	... ต่อด้วย bd,be,bf

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def letter_combinations(digits):
    if not digits:
        return []                     # ไม่มีเลขก็ไม่มีชุดตัวอักษร
    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    result = []
    path = []                         # ตัวอักษรที่เลือกไว้แล้วในเส้นทางนี้

    def backtrack(i):
        if i == len(digits):          # เลือกครบทุกหลักแล้ว
            result.append("".join(path))  # ต่อ path เป็นสตริงเก็บคำตอบ
            return
        for ch in mapping[digits[i]]: # ลองทุกตัวอักษรบนปุ่มนี้
            path.append(ch)           # choose
            backtrack(i + 1)          # explore หลักถัดไป
            path.pop()                # unchoose ถอยไปลองตัวอื่น

    backtrack(0)
    return result

print(letter_combinations("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
print(letter_combinations(""))   # []

Output

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
[]

เราเดินตาม digit ของ digits ทีละตัวด้วย pointer (ตัวชี้) i ที่ digit ตำแหน่ง i เราดูว่าปุ่มนั้นมีตัวอักษรอะไรบ้าง (mapping[digits[i]]) แล้ว iterate ลองทุกตัว แต่ละตัวคือหนึ่ง branch ของ tree เมื่อ i เดินไปถึง length ของ digits แปลว่าเรา choose ครบทุก digit แล้ว จึง join path เป็น string เก็บลง result

ถ้าลองเอา path.pop() ออก จะเกิดอะไรขึ้น? path จะยาวขึ้นเรื่อย ๆ ไม่มีวันสั้นลง ทำให้เงื่อนไข i == len(digits) กับ length ของ path ไม่ตรงกัน และตัวอักษรจาก branch เก่าจะค้างมาปน branch ใหม่ คำตอบเพี้ยนทันที การ pop() คือการ restore (คืนสภาพ) path ให้เท่าเดิมก่อน branch นี้

Time O(4^n · n) เมื่อ n คือจำนวน digit แต่ละ digit แตกได้มากสุด 4 branch (ปุ่ม 7 กับ 9 มี 4 ตัว) จึงมีคำตอบได้ถึง 4^n ชุด และการ join string แต่ละชุดใช้เวลา O(n) · Space O(n) จาก depth ของ recursion และขนาด path (ไม่นับพื้นที่เก็บ result)

💡 สรุป pattern

เมื่อต้อง build ทุกชุดคำตอบที่ประกอบจากการ choose ทีละ position (ตำแหน่ง) ให้ใช้ recursion แทนการซ้อน for โดย depth = จำนวน position และ iterate choice ที่ position นั้นด้วยจังหวะ choose/explore/unchoose