Letter Combinations of a Phone Number ใน Python - รูปแบบตัวอักษรจากหมายเลขโทรศัพท์

สมมติว่าเรามีสตริงที่มีตัวเลข 2-9 เราต้องคืนการจัดหมู่ตัวอักษรทั้งหมดที่หมายเลขอาจแทนได้ Mapping ตัวเลขไปตัวอักษร (เหมือนปุ่มโทรศัพท์):

1	2 a b c	3 d e f
4 g h i	5 j k l	6 m n o
7 p q r s	8 t u v	9 w x y z
*	0	#

ตัวอย่าง "23" สตริงที่เป็นไปได้: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

ขั้นตอนการทำงาน (Recursive Backtracking)

กำหนดฟังก์ชัน solve แบบ recursive
solve รับ digits, characters, result, current_string, current_level:
- ถ้า current_level == len(digits) ใส่ current_string ลง result คืนค่า
- วนลูปทุก i ใน characters[digits[current_level]]:
  - เรียก solve(digits, characters, result, current_string + i, current_level + 1)
ฟังก์ชันหลัก:
- ถ้า len(digits) == 0 คืนลิสต์ว่าง
- กำหนด map ตัวเลข-ตัวอักษร
- result := []
- เรียก solve(digits, characters, result, "", 0)

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

class Solution(object):
    def letterCombinations(self, digits):
        if len(digits) == 0:
            return []
        characters = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
        result = []
        self.solve(digits, characters, result)
        return result

    def solve(self, digits, characters, result, current_string="", current_level=0):
        if current_level == len(digits):
            result.append(current_string)
            return
        for i in characters[int(digits[current_level])]:
            self.solve(digits, characters, result, current_string+i, current_level+1)

ob1 = Solution()
print(ob1.letterCombinations("37"))

อินพุต

"37"

เอาต์พุต

["dp","dq","dr","ds","ep","eq","er","es","fp","fq","fr","fs"]