from typing import List
import collections
# 這道題可以用深搜或者廣搜來解決
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
##先定義數字和字母的字典
dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
# 定義變數用來接收最后的結果
self.res = []
# 如果字串為空就回傳空
if len(digits) == 0:return self.res
# 定義一個雙端佇列，
deque = collections.deque()
# 注意這里，要添加一個為空的東西，
deque.append("")
# 進行遍歷，首先需要遍歷傳入的字串，
for index1 in range(len(digits)):
# 然后遍歷次數為雙端佇列的長度，
for index2 in range(len(deque)):
# 取得每一個數字對應的字母的值，
now_str = dic[digits[index1]]
print(now_str)
# 將佇列最左端的字符踢出，用來和對應字母相加，
now_deque_str = deque.popleft()
# 遍歷每一個數字對應的字母
for index3 in now_str:
print(111)
# 注意這里，是要把剛才最左端踢出的字串，在和index3字符相加
# 然后添加進佇列的最右端，
deque.append(now_deque_str + index3)
print("當前佇列的值",deque)
return list(deque)
# 這是用的遞回的方法，
def letterCombinations1(self, digits: str) -> List[str]:
# 同樣需要先定義一個字典，用來表示數字對應的字母
dic = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
# 定義變數用來接收最后的字串，
self.res = []
if len(digits) == 0: return self.res
self.dfs(dic,digits,"",0)
return self.res
def dfs(self,dic,digits,now_str,depth):
# dic:自己定義的字典，digits:入參的字串，
# now_str：遞回用來接收字串的變數
# depth:深度，
if depth == len(digits):
self.res.append(now_str)
return
# 這里只有一步就好了，
for letter_str in dic[digits[depth]]:
self.dfs(dic,digits,now_str + letter_str,depth + 1)
A = Solution()
print(A.letterCombinations1("2"))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20963.html
標籤：Python