Letter Combinations of a Phone Number

这道题就是典型的回溯问题了，而且是属于比较简单的一类，因为没有查重问题的存在（每个字符的位置是固定的不可变换）使得整个题目就是套回溯的模板就能解决了，另外需要注意空列表时需要单独返回，下面是代码

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        look_up_table = {'0' : [' '], '1' : ['*'], '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']}

        tmp, res = [], []
        self.helper(0, len(digits), look_up_table, tmp, res, digits)
        return res

    def helper(self, start, end, checker, tmp, res, string):
        if start == end:
            ref = tmp[:]
            res.append(''.join(ref))
            return 

        for ch in checker[string[start]]:
            tmp.append(ch)
            self.helper(start + 1, end, checker, tmp, res, string)
            tmp.pop()