leetcode17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

方法一：回溯

回溯是通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

给出如下回溯函数backtrack(combination, next_digits)，它将一个目前已经产生的组合combination和接下来准备要输入的数字next_digits作为参数。

如果没有更多的数字需要被输入，那意味着 当前的组合产生好了。
如果还有数字需要被输入：
遍历下一个数字所对应的所有映射的字母。
将当前的字母添加到组合最后，也就是combination=combination+letter。
重复这个过程，输入剩下的数字：backtrack(combination + letter, next_digits[1:])。

代码

class Solution:
    def letterCombinations(self, digits):
        phone = {
            '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']
        }
        def backtrack(combination, next_digits):
            if len(next_digits) == 0:
                output.append(combination)
            else:
                print(next_digits)
                print(next_digits[0])
                for i in phone[next_digits[0]]:
                    backtrack(combination+i, next_digits[1:])


        output = []
        if digits:
            backtrack("", digits)
        return output

方法二：队列

我们可以利用队列的先进先出特点，再配合循环完成题目要求。
我们先将2对应的字符”a”,”b”,”c”依次放入队列中

之后再从队列中拿出第一个元素”a”，跟3对应的字符”d”,”e”,”f”挨个拼接

拼接结束后队列中的存储情况：

按照同样的方式，再将”b”从队列中拿出，再跟3对应的字符”d”,”e”,”f”挨个拼接，放回队列中：

动态演示如下：

代码

class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []
        d = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        # 队列初始化，放入一个空字符
        res = [""]
        for i in digits:
            size = len(res)
            letters = d[ord(i) - 48]
            # 计算出队列长度后，将队列中的每个元素逐个取出
            for _ in range(size):
                tmp = res.pop(0)
                for j in letters:
                    res.append(tmp + j)
        return res

差不多，bfs和dfs的区别把，今日打卡完结~

参考资料

官方题解
队列