425. 电话号码的字母组合

class Solution:
    """
    @param digits: A digital string
    @return: all posible letter combinations
    """
    def letterCombinations(self, digits):
        # write your code here
        #bfs一圈圈的匹配
        if not digits: return []
        
        #初始化
        queue = []
        dict = {‘2‘:‘abc‘,‘3‘:‘def‘,‘4‘:‘ghi‘,‘5‘:‘jkl‘,‘6‘:‘mno‘,‘7‘:‘pqrs‘,‘8‘:‘tuv‘,‘9‘:‘wxyz‘}
        
        #先把第一个值放进去
        first_num = digits[0]
        for i in dict[first_num]:
            queue.append(i)
        
        
        #后面的值加进去
        for i in digits[1: ]:
            res = []
            while queue:
                cur_s = queue.pop(0)
                
                for j in dict[i]:
                    new_s = cur_s + j 
                    res.append(new_s)
            queue = res 

        return queue