Giả sử chúng ta có một chuỗi chứa các chữ số từ 2-9. Chúng tôi phải tìm tất cả các kết hợp chữ cái có thể có mà số đó có thể tạo ra. Dưới đây là một ánh xạ từ chữ số sang chữ cái (giống như trên các nút điện thoại). Lưu ý rằng 1 ánh xạ một số ký tự nhưng không có chữ cái.
| 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 | # |
Ví dụ:nếu chuỗi đã cho là “49”, thì các chuỗi có thể có sẽ là ['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz ',' iw ',' ix ',' iy ',' iz ']
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- Xác định một mảng được gọi là giải quyết để giải quyết vấn đề một cách đệ quy
- phương thức giải quyết nhận các chữ số, ký tự, kết quả, current_string và current_level, hàm sẽ như thế nào
- nếu current_level =độ dài của các chữ số, sau đó thêm chuỗi hiện tại vào sau kết quả và trả về
- cho tất cả các ký tự i trong các ký tự [chữ số [current_level]]
- thực hiện giải quyết (chữ số, ký tự, kết quả, current_string + i, current_level + 1)
- Chức năng thực tế sẽ như thế nào
- nếu độ dài các chữ số là 0, thì trả về danh sách trống
- xác định một bản đồ để chứa các số và ký tự tương ứng dưới dạng một chuỗi
- kết quả:=một danh sách trống
- gọi giải quyết (chữ số, ký tự, kết quả, “”, 0)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
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']