Tổ hợp chữ cái của số điện thoại trong Python

Giả sử chúng ta có một chuỗi chứa các chữ số từ 2-9. Chúng ta phải trả về tất cả các tổ hợp chữ cái có thể mà số đó đại diện. Một ánh xạ chữ số sang chữ cái (giống như trên bàn phím điện thoại) được cho dưới đây. Lưu ý 1 không ánh xạ đến bất kỳ chữ cái nào.

Ví dụ, nếu chuỗi cho trước là "23", các chuỗi có thể sẽ là ["ad","ae","af","bd","be","bf","cd","ce","cf"].

Để giải quyết, chúng ta làm theo các bước sau:

• Định nghĩa hàm solve để giải quyết bằng đệ quy.
• Hàm solve nhận digits, characters, result, current_string và current_level, hàm sẽ như sau:
  • Nếu current_level == độ dài digits, thêm current_string vào result, và trả về.
  • Với mỗi ký tự i trong characters[digits[current_level]]:
    • Gọi solve(digits, characters, result, current_string + i, current_level + 1).
• Hàm thực tế sẽ như sau:
  • Nếu độ dài digits là 0, trả về danh sách rỗng.
  • Định nghĩa một bản đồ ánh xạ số và chuỗi ký tự tương ứng.
  • result := danh sách rỗng.
  • Gọi solve(digits, characters, result, "", 0).

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

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

Đầu vào

"37"

Đầu ra

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