Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

思路
for x N : 不明智 -> X
所以 遞迴 (感覺還可以再找找其他非遞迴的) <-- 總覺得遞迴不好想
Start : 第一個數字開始
傳進 dfs 那傳哪些參數呢 :

• 整串數字:digits
• 目前誰當頭,以哪個數字為主去和其他數字組:index
• 暫時性結果用來判斷是否已組出一組解: tmp
• 最終解 就是每當暫時性結果組出一組時就 加進去: rlist

dfs 兩件事

1. 決定何時 return : 暫時性結果 組出一組解時, 也就是說 tmp 長度 == index
2. 丟一個數字 查MAP 知有哪些子母可以對應 , + 進 tmp , 再呼叫 dfs (...index+1...)
   2-1. 暫時性離開
   2-2. 回來時 踢除最後一個 letter , 換其他letter
   2-3. 由 數字對應還沒用過的 letter 補上
   End: 最後 確認結果 checkit , return 答案 (rlist)

Note :

• Member function 之前的呼叫用法
• global variable 使用

正解

MAP = {}
MAP[0] = ""
MAP[1] = ""
MAP[2] = "abc"
MAP[3] = "def"
MAP[4] = "ghi"
MAP[5] = "jkl"
MAP[6] = "mno"
MAP[7] = "pqrs"
MAP[8] = "tuv"
MAP[9] = "wxyz"
#rlist = []
class Solution:

        
    def dfs(self,digits: str,index: int,tmp:str,rlist:[])-> List[str]:
        global MAP
        if index == len(digits):
            rlist.append(tmp)
            print(rlist)
            return rlist
        mValue = MAP[int(digits[index])]
        for i in range(len(mValue)):
            tmpc = mValue[i]
            tmp+=tmpc
            self.dfs(digits,index+1,tmp,rlist)
            tmp = tmp[:len(tmp)-1]
        #print("call me maybe")
        #print(rlist)
        #return rlist
    def letterCombinations(self, digits: str) -> List[str]:
        # call dfs()
        # pass
        # digits = "hello"
        #global rlist
        index  =  0
        tmp = ""
        
        rlist = []
        if len(digits)==0:
            return []
        self.dfs(digits,index,tmp,rlist)
        print("checkit"+str(rlist))
        return rlist        

Result