电话号码的字母组合 力扣第17题:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
示例:
输入：”23”
1. 回溯
首先看一看数字对应的可能是3个字母或是4个字母。所以可以构建列表或者哈希表，因为列表的话索引值需要转化，所以适合构建哈希表。
给出如下回溯函数 backtrack(combination, next_digits) ，它将一个目前已经产生的组合 combination 和接下来准备要输入的数字 next_digits 作为参数。
一个数字下面有三或4中可能，所以每一种可能都要穷举出来，每递归一层输入的字符串就减小一个长度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution : def letterCombinations (self, digits: str) -> List[str]: if not digits: return [] phone = { '2' : 'abc' , '3' : 'def' , '4' : 'ghi' , '5' : 'jkl' , '6' : 'mno' , '7' : 'pqrs' , '8' : 'tuv' , '9' : 'wxyz' , } def backtrack (combination, next_digits) : if len(next_digits) == 0 : output.append(combination) else : for letter in phone[next_digits[0 ]]: backtrack(combination + letter, next_digits[1 :]) output = [] if digits: backtrack("" , digits) return output
复杂度分析 时间复杂度: O((3^N)*(4^M)),其中N为对应3个字母的数字,M为对应4个字母的数字。
空间复杂度： O((3^N)*(4^M))，每一个结果都需要保存。
队列
作者：z1mhttps://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/
使用队列，先将输入的 digits 中第一个数字对应的每一个字母入队，然后将出队的元素与第二个数字对应的每一个字母组合后入队…直到遍历到 digits 的结尾。最后队列中的元素就是所求结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def letterCombinations (self, digits: str) -> List[str]: if not digits: return [] phone = { '2' : 'abc' , '3' : 'def' , '4' : 'ghi' , '5' : 'jkl' , '6' : 'mno' , '7' : 'pqrs' , '8' : 'tuv' , '9' : 'wxyz' , } queue = ['' ] for digit in digits: for _ in range(len(queue)): tmp = queue.pop(0 ) for char in phone[digit]: queue.append(tmp + char) return queue
复杂度分析 时间复杂度: O((3^N)*(4^M)),其中N为对应3个字母的数字,M为对应4个字母的数字。
空间复杂度： O((3^N)*(4^M))，每一个结果都需要保存。
