Leetcode 17.电话号码的字母组合

题目描述

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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

输入：digits = ""
输出：[]

解题思路

本题是一道非常经典的回溯题

如果你对回溯没有任何学习过 你可以按照我说的做

首先我们看第一个示例

是两个数字2和3 我们可以在上面图片找到对应字母abc和def

这样的话我们可以写一个双for循环

for i in "abc":
    for j in "def":
        print(i+j)

那你可以说直接手写一堆for不就行了？ 但是当数字逐渐增多的时候 或者不能知道下一个数是什么

可以转化成二叉树问题

这个时候就可以用到我们前面学的递归+深度优先搜索了 通过递归可以实现多重循环

于是我们可以这样写

def dfs(i,ans): # i是当前的字母 ans是答案
    for j in i:
        ans+=i # 添加当前枚举的答案
        dfs(i+1,ans) # 继续深入 达到最底
        ans-=i # 回溯 还原之前的答案 这样做是取下一个字母 如果不还原答案 会出现重复

那么递归的边界是什么？

当前答案长度==字母串的长度时这个时候就可以return了

总之回溯就是暴力算法 相当于试探 当试探完之后会撤销选择 继续下一次选择

示例代码

num = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        ans = []
        k = len(digits)
        def dfs(i,temp):
            if k == len(temp):
                ans.append("".join(temp))
                return
            for a in num[int(digits[i])]:
                temp.append(a)
                dfs(i+1,temp)
                temp.pop()
        dfs(0,[])
        return ans

// 转载的代码
class Solution {
public:
    string s;
    vector<string> result;
    //设置一个字符串数组进行映射
    vector<string> letterMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void backtracking(string &digits, int index) {
        if (index == digits.size()) {
            result.emplace_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); ++i) {
            s.push_back(letters[i]);
            backtracking(digits, index + 1);
            s.pop_back();
        } 
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return result;
        backtracking(digits, 0);
        return result;
    }
};

感谢收看