Chương trình tìm tất cả chuỗi ký tự có thể gõ từ bàn phím điện thoại bằng Python

Cho chuỗi số 2-9. Tìm tất cả tổ hợp chữ cái tương ứng (như bàn phím điện thoại cũ).

Ví dụ: "49" → ['gw','gx','gy','gz','hw','hx','hy','hz','iw','ix','iy','iz'].

Giải thuật

• Đệ quy: hàm solve(digits, chars, result, current_string, current_level).
• Nếu current_level == len(digits): thêm current_string vào kết quả.
• Ngược lại: lặp qua các chữ cái của digits[current_level], gọi đệ quy với current_level+1.

Ví dụ minh họa

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("49"))

Đầu vào

"49"

Đầu ra

['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']