###### tags: `Leetcode` `medium` `backtracking` `python` `Top 100 Liked Questions`

# 17. Letter Combinations of a Phone Number

## [題目連結:] https://leetcode.com/problems/letter-combinations-of-a-phone-number/

## 題目:
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in **any order**.

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


**Example 1:**

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

**Example 2:**

Input: digits = ""
Output: []

**Example 3:**

Input: digits = "2"
Output: ["a","b","c"]

#### [圖片來源:]https://leetcode.com/problems/letter-combinations-of-a-phone-number/

## 解題想法:
* 題目為:按數字，輸出其所有字母組合
* 字典存
* key:數字
* val:其對應的字母

## Python:(Sol1: DFS)
* cur紀錄當前經過的邊
* cur初始為["",""]表示:
* 可以存兩個值 :根據len(len(digits))=2
* 遍歷順序:
* ex: 走到a點:紀錄["a",""]
* 再往下走到d點:["a","d"]->此邊以探索完畢 輸出["ad"]
* 退回a 在往下走到e點:["a","e"]->此邊以探索完畢 輸出["ae"]

class Solution:
    #法1: DFS
    def letterCombinations(self, digits): 
        map = {"2":"abc", 
               "3":"def", 
               "4":"ghi", 
               "5":"jkl", 
               "6":"mno", 
               "7":"pqrs", 
               "8":"tuv",
               "9":"wxyz"}
        cur = [""]*len(digits)
        self.ans = []
        self.dfs(digits,map,0,cur)
        return self.ans
    
    def dfs(self,digits,map,layer,cur):
        #已到最底了 將值加入到ans
        if layer==len(digits):
            if layer>0:
                self.ans.append("".join(cur))
            #return None
        #取該layer的值
        #ex: layer=0 即取digits[0]=2 的value-> a,b,c
        else:
            for value in map[digits[layer]]:
                #將目前的值存入該層
                cur[layer]=value
                #搜尋下一層
                self.dfs(digits,map,layer+1,cur)

if __name__ == '__main__':
    result = Solution()
    digits = "23"
    ans = result.letterCombinations(digits)
    print(ans)
    #Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

## Python: (Sol2: BFS)

class Solution:
    def letterCombinations(self, digits):
        #bfs
        if not digits: 
            return []      
        map = {"2":"abc",
               "3":"def",
               "4":"ghi", 
               "5":"jkl", 
               "6":"mno", 
               "7":"pqrs", 
               "8":"tuv",
               "9":"wxyz"}
        ans = [""]
        for layer in digits:
            #layer='2','3'
            tmp = []
            for pre_val in ans:
                #第一次進來 pre_val=""
                #下一次近來 pre_val即逐一為上層的值'a','b','c'
                for cur_val in map[layer]:
                    #cur_val為該層的值 ex:map[2]-> a,b,c
                    tmp.append(pre_val + cur_val)
            #跑完第一次回圈tmp最終為第一層的值:
            #tmp = ['a','b','c']
            #更新給ans
            ans = tmp
      
        return ans
    
if __name__ == '__main__':
    result = Solution()
    digits = "23"
    ans = result.letterCombinations(digits)
    print(ans)