博客

1、题目描述：

2、题解：

方法1：深度优先搜索DFS | 回溯


这个题就是穷举，把所有情况都穷举一遍，因此用回溯法。

回溯算法框架：
    res = []
    def backtrack(路径，选择列表)：
        做剪枝
        if 满足结束条件：
            res.append(路径)
            return
        for 选择 in 选择列表：
            做选择
            backtrack(路径，选择列表)
            撤销选择

解决一个回溯问题，实际上就是一个决策树的遍历过程：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

Python实现：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {
            '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'
        }

        # 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']}#做Hashb映射     
        def backtrack(path,start):
            if len(path) == len(digits):
                res.append(''.join(path))
                return
            for i in phone[digits[start]]:
                path.append(i)
                backtrack(path,start+1)  
                path.pop()
         res = []
        if digits:
            backtrack([], 0)
        return res  

也可以这样：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {
            '2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'
        }

        # 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']}#做Hashb映射     
        def backtrack(path,start):
            if len(path) == len(digits):
                res.append(path)
                return
            for i in phone[digits[start]]:
                backtrack(path + i,start+1)  
        res = []
        if digits:
            backtrack('', 0)
        return res    

C++实现：

class Solution {
public:
    map<char,string> phone = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
        {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    vector<string> letterCombinations(string digits) {
        //回溯
        vector<string> res;
        string path;
        if (digits.size()){
            backtrack(0,path,digits,res);
        }
        return res;
    }
    void backtrack(int start,string path,string digits,vector<string>& res){
        if (path.size() == digits.size()){
            res.push_back(path);
            return;
        }
        for (char i : phone[digits[start]]){
            path.push_back(i);
            backtrack(start+1,path,digits,res);
            path.pop_back();
        }
    }
};

3、复杂度分析：