Leetcode 17. Letter Combof a Phone Num 两种解法

Naive BFS %39
    这个题目用PYTHON可以秒解，下面的解法很NAIVE，但是应该属于BFS：
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        
        # BFS
        if not digits:
            return []
        keyMap = {
            '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']
            }
        self.L = len(digits)
        res = []
        for d in digits:
            if not res:
                res = keyMap[d]
            else:
                res = [p+c for p in res.copy() for c in keyMap[d] ]
        return res

DFS 74%
    DFS确实快很多，关键之处是只对每个键对应的字母进行循环 ：
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        self.keyMap = {
            '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']
            }
        self.L = len(digits)
        res = []
        self.DFS(digits, 0, '', res)
        return res
   
    def DFS(self, digits, indx, substr, res):
        if len(substr) == self.L:
            res.append(substr[:])
            return
        
        for c in self.keyMap[digits[indx]]:               
            substr = '{}{}'.format(substr, c)
            #print (c, substr)
            self.DFS(digits, indx+1, substr, res)
            substr = substr[:-1]

更正一下， 上面的解法BFS慢是因为用了COPY，刚才又提交了一个不用COPY的版本， 更快了 ，所以这道题非要归类为BACKTRACKING是有 勉强了：                                                                                    
NAIVE BFS　％９３：
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # BFS
        if not digits:
            return []
        keyMap = {
            '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']
            }
        self.L = len(digits)
        res = []
        for d in digits:
            if not res:
                res = keyMap[d]
            else:
                res = [p+c for p in res for c in keyMap[d] ]
        return res