#P4070. 电话号码的字母组合
-
ID: 2311
Tried: 99
Accepted: 28
Difficulty: 5
电话号码的字母组合
题目内容
给定一个仅包含数字 2−9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1不对应任何字母。
输入描述
输入一个字符串 digits，字符串长度在 0 到 4 之间，且每个字符为 2 到 9 之间的数字。
输出描述
输出所有可能的字母组合，每个字母组合为一个字符串，输出结果按任意顺序返回。
样例1
输入：
23
输出：
ad ae af bd be bf cd ce cf
样例2
输入：
""
输出：
提示
- 0≤digits.length≤4
- digits[i]是范围 ['2', '9'] 的一个数字。
解题思路
给定一个数字字符串，每个数字对应若干字母，我们的目标是找到所有这些数字组合的字母排列。解决方案可以用回溯法、递归、或迭代来生成所有的组合。
具体思路：
-
映射关系：首先，根据给定的数字与字母的映射关系（如电话键盘的映射），我们需要知道每个数字（2-9）对应哪些字母。
-
递归/回溯：我们可以从第一个数字开始，选择其所有可能的字母，然后递归地为后续的数字选择字母。通过这种方式，我们会生成所有字母组合。
-
边界条件：如果输入为空字符串，则直接返回空列表。
-
返回结果：将所有组合生成后，返回最终的字母组合列表。
Python 版本
# 电话键盘映射
phone_map = {
'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 letter_combinations(digits):
if not digits: # 如果输入为空字符串，直接返回空列表
return []
result = [''] # 初始化结果列表，开始为空字符串
for digit in digits: # 遍历每个数字
letters = phone_map[digit] # 获取当前数字对应的字母
# 对于当前结果中的每个组合，追加字母
result = [prefix + letter for prefix in result for letter in letters]
return result # 返回最终结果
# 输入
digits = input().strip()
# 获取所有字母组合并输出
combinations = letter_combinations(digits)
print(" ".join(combinations)) # 输出以空格分隔的字母组合
Java 版本
import java.util.*;
public class Main {
// 电话键盘映射
private static final Map<Character, String> phoneMap = new HashMap<>();
static {
phoneMap.put('2', "abc");
phoneMap.put('3', "def");
phoneMap.put('4', "ghi");
phoneMap.put('5', "jkl");
phoneMap.put('6', "mno");
phoneMap.put('7', "pqrs");
phoneMap.put('8', "tuv");
phoneMap.put('9', "wxyz");
}
public static List<String> letterCombinations(String digits) {
if (digits.isEmpty()) { // 如果输入为空字符串，返回空列表
return new ArrayList<>();
}
List<String> result = new ArrayList<>();
result.add(""); // 初始化结果列表，从空字符串开始
for (char digit : digits.toCharArray()) { // 遍历每个数字
String letters = phoneMap.get(digit); // 获取当前数字对应的字母
List<String> temp = new ArrayList<>();
for (String prefix : result) { // 遍历当前组合
for (char letter : letters.toCharArray()) {
temp.add(prefix + letter); // 组合字母
}
}
result = temp; // 更新结果
}
return result; // 返回所有字母组合
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String digits = sc.nextLine().trim();
List<String> combinations = letterCombinations(digits);
System.out.println(String.join(" ", combinations)); // 输出以空格分隔的字母组合
}
}
C++ 版本
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 电话键盘映射
unordered_map<char, string> phone_map = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
vector<string> letterCombinations(string digits) {
if (digits.empty()) { // 如果输入为空字符串，返回空列表
return {};
}
vector<string> result = {""}; // 初始化结果列表，从空字符串开始
for (char digit : digits) { // 遍历每个数字
string letters = phone_map[digit]; // 获取当前数字对应的字母
vector<string> temp;
for (const string& prefix : result) { // 遍历当前组合
for (char letter : letters) {
temp.push_back(prefix + letter); // 组合字母
}
}
result = temp; // 更新结果
}
return result; // 返回所有字母组合
}
int main() {
string digits;
getline(cin, digits); // 输入
vector<string> combinations = letterCombinations(digits);
for (const string& comb : combinations) {
cout << comb << " "; // 输出以空格分隔的字母组合
}
cout << endl;
return 0;
}