leetcode 17 电话号码

通过迭代方法
数组赋值的时候需要注意。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        hashmap=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']

        alpha=[]
        for i in digits:
            alpha.append(hashmap[int(i)])


        res=[]
        result=[]


        for i in range(len(alpha[0])):
            res.append(alpha[0][i])
        for item in alpha[1:]:

            for t in item:
                result+=[num+t for num in res]
            #print(result)
            res[:]=result[:]
            result[:]=[]
            #print(res)

        return res

递归的方法
其中将每一个数字对应的字母看成递归树的一层

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        hashmap=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']

        def dfs(i,path,result):

            if i == len(digits):
                result.append(path[:])
                return 
            hashnode=hashmap[int(digits[i])]
            for j in range(len(hashnode)):

                dfs(i+1,path+hashnode[j],result)

        result=[]
        dfs(0,'',result)
        return result

队列的方法，初始化时将queue中放置一个空字符串，然后每次循环以队列的长度，因为那是上轮的结果的数量（数组长度）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        hashmap=['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        queue=['']        

        for i in range(len(digits)): 
            for _ in range(len(queue)):
                s=queue[0]
                queue[:]=queue[1:]           
                for j in hashmap[int(digits[i])]:

                    queue.append(s+j)

        return queue

这里放一个其他题解的方法，使用递归，也可以把digits对应的字母设置为数组形式，然后最后递归记录（返回）结果的时候，通过"".join()

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()

        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(index: int):
            if index == len(digits):
                combinations.append("".join(combination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()
        combinations = list()
        backtrack(0)
        return combinations

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。