17. Letter Combinations of a Phone Number 电话号码的字母组合

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：电话号码, 字母组合，回溯法，题解，leetcode, 力扣，Python, C++, Java

@TOC

# 题目描述

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

A mapping 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.

# 解题方法

# 回溯法

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)
``````

``````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"}};
};
``````

# 内置函数

``````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'}
for each in product(*[kvmaps[key] for key in digits]):
``````

# 循环

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
``````

# 日期

2018 年 2 月 24 日 2018 年 12 月 21 日 —— 一周就要过去了 2019 年 1 月 8 日 —— 别熬夜，我都开始有黑眼圈了。。