本文关键词：电话号码, 字母组合，回溯法，题解，leetcode, 力扣，Python, C++, Java

题目地址：https://leetcode.com/problems/generate-parentheses/description/

题目描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

Amapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

题目大意

在拨号键盘上按下了几个键，问能打出来的字符串的所有组合是多少。

解题方法

回溯法

依然是回溯法。要求所有的可能的字符串的组合。

有点类似784. Letter Case Permutation，不需要对index进行for循环，因为对index进行for循环产生的是所有可能的组合。而这两个题要求的组合的长度是固定的，每个位置都要有字母。

另外就是要判断一下path != ''，原因是当 digits 为""的要求的结果是 [] ，而不是 [""] 。

Python代码如下：

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        kvmaps = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        res = []
        self.dfs(digits, 0, res, '', kvmaps)
        return res
    
    def dfs(self, string, index, res, path, kvmaps):
        if index == len(string):
            if path != '':
                res.append(path)
            return
        for j in kvmaps[string[index]]:
            self.dfs(string, index + 1, res, path + j, kvmaps)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

如果不新增函数，而是直接使用题目给出的函数，也可以很快写出代码。唯一要注意的是，当题目输入为""的时候，要返回{}，那么for循环就没法遍历，所以我给他添加成了{""}，这样循环就能进行了。

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return {};
        vector<string> res;
        for (char d : board[digits[0]]) {
            auto next = letterCombinations(digits.substr(1));
            if (next.size() == 0)
                next.push_back("");
            for (string n : next) {
                res.push_back(d + n);
            }
        }
        return res;
    }
private:
    unordered_map<char, string> board = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

内置函数

使用python 自带的product笛卡尔乘积函数。

from itertools import product
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        kvmaps = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        answer = []
        for each in product(*[kvmaps[key] for key in digits]):
            answer.append(''.join(each))
        return answer

1 2 3 4 5 6 7 8 9 10 11 12 13 14

循环

使用循环也能轻松把这个题目给搞定。使用结果数组res表示遍历到当前的位置已有的结果，那么再遍历下一个位置的时候，把这个位置能形成的所有结果和原来的进行两两组合。

python代码如下：

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "": return []
        d = {'2' : "abc", '3' : "def", '4' : "ghi", '5' : "jkl", '6' : "mno", '7' : "pqrs", '8' : "tuv", '9' : "wxyz"}
        res = ['']
        for e in digits:
            res = [w + c for c in d[e] for w in res]
        return res

1 2 3 4 5 6 7 8 9 10 11 12

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发