LeetCode第十七题：电话号码的字母组合
- 学习
- 2024-02-29
- 43热度
- 0评论
题目来源：LeetCode第十七题
1.题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题思路
解法一：回溯法
- 描述：准备一个映射表来将数字映射到对应的字母串，一个临时字符串用于存储当前的组合，和一个动态数组用于存储所有可能的组合。从输入的第一个数字开始，对于每个数字，根据映射表找到对应的所有可能的字母。遍历这些字母，将每个字母依次加入到当前的组合字符串中。对于加入了新字母的当前组合，递归地调用回溯函数，处理下一个数字。如果当前组合的长度等于输入数字串的长度，说明找到了一个完整的组合，将其加入到结果集中。在返回到上一层递归之前，撤销最后一步的选择（即从当前组合中移除最后一个字母），以便尝试其他可能的字母。
- 时间复杂度：
O(3^m * 4^n)。m和n分别代表输入数字中对应3个字母的数字个数和对应4个字母的数字个数。 - 空间复杂度：
O(m + n)。递归的最大深度等于输入数字字符串的长度，即m + n。因此，递归调用栈占用的空间是O(m + n)。 - 参考代码：
java版：
class Solution {
// 数字到字母的映射
private static final Map<Character, String> phoneMap = Map.of('2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
public List<String> letterCombinations(String digits) {
// 存放所有字母组合
List<String> combinations = new ArrayList<>();
// 如果输入为空，则直接返回空的结果列表
if (digits == null || digits.length() == 0) {
return combinations;
}
// 开始回溯过程，从第0个索引和空的当前组合字符串开始
backtrack(combinations, digits, 0, new StringBuilder());
return combinations;
}
// 回溯方法
private void backtrack(List<String> combinations, String digits, int index, StringBuilder combination) {
// 如果当前索引等于数字字符串的长度，意味着已经处理完所有数字，当前组合完成
// 例如23 处理2的a后索引为1，然后处理3的d，索引为2，继续回溯的时候index=digits.length()
// 就把ad加入组合中
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
// 获取当前数字
char digit = digits.charAt(index);
// 在Map中找这个数字对应的字符串
String letters = phoneMap.get(digit);
// 遍历当前数字对应的字符串的所有字母
for (char letter : letters.toCharArray()) {
// 将当前字母添加到组合中
combination.append(letter);
// 递归调用，处理下一个数字
backtrack(combinations, digits, index + 1, combination);
// 回溯：撤销上一步的选择（删除组合中的最后一个字母），尝试下一个可能的字母
combination.deleteCharAt(index);
}
}
}
}C++版：
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
// 如果输入为空，则直接返回空的结果列表
if (digits.empty()) {
return combinations;
}
// 数字到字母的映射
unordered_map<char, string> phoneMap{
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
string combination;
// 开始回溯过程，从第0个索引和空的当前组合字符串开始
backtrack(combinations, phoneMap, digits, 0, combination);
return combinations;
}
private:
void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap,
const string& digits, size_t index, string& combination) {
// 如果当前索引等于数字字符串的长度，意味着已经处理完所有数字，当前组合完成
// 例如23 处理2的a后索引为1，然后处理3的d，索引为2，继续回溯的时候index=digits.length()
// 就把ad加入组合中
if (index == digits.size()) {
combinations.push_back(combination);
}
else {
// 获取当前数字
char digit = digits[index];
// 在Map中找这个数字对应的字符串
const string& letters = phoneMap.at(digit);
// 遍历当前数字对应的字符串的所有字母
for (char letter : letters) {
// 将当前字母添加到组合中
combination.push_back(letter);
// 递归调用，处理下一个数字
backtrack(combinations, phoneMap, digits, index + 1, combination);
// 回溯：撤销上一步的选择（删除组合中的最后一个字母），尝试下一个可能的字母
combination.pop_back();
}
}
}
};C版：
// 电话号码映射表
const char* map[10] = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
void backtrack(char* digits, char** combinations, char* temp, int index, int* returnSize, int digitsLen) {
// 当前组合完成，复制到combinations中
if (index == digitsLen) {
combinations[*returnSize] = (char*)malloc((digitsLen + 1) * sizeof(char));
strcpy(combinations[*returnSize], temp);
(*returnSize)++;
return;
}
// 获取当前数字对应的字母字符串，并遍历
const char* letters = map[digits[index] - '0'];
for (int i = 0; letters[i] != '\0'; i++) {
temp[index] = letters[i]; // 将当前字母加入到当前组合中
backtrack(digits, combinations, temp, index + 1, returnSize, digitsLen); // 递归处理下一个数字
temp[index] = '\0'; // 回溯，撤销上一步的选择
}
}
char** letterCombinations(char* digits, int* returnSize) {
*returnSize = 0;
int digitsLen = strlen(digits);
if (digitsLen == 0) {
return NULL;
}
// 预估结果的最大数量，以便分配足够的内存（最多4^长度）
int maxCombinations = 1;
for (int i = 0; i < digitsLen; i++) {
if (digits[i] == '7' || digits[i] == '9') {
maxCombinations *= 4;
}
else {
maxCombinations *= 3;
}
}
char** combinations = (char**)malloc(maxCombinations * sizeof(char*));
char* temp = (char*)malloc((digitsLen + 1) * sizeof(char));
temp[digitsLen] = '\0'; // 确保字符串正确结束
backtrack(digits, combinations, temp, 0, returnSize, digitsLen);
free(temp); // 释放临时字符串的内存
return combinations;
}解法二：迭代法
- 描述：创建一个动态数组或列表以存储字符串组合，初始时仅包含一个空字符串。逐个处理输入字符串（电话号码）中的每个数字。对于每个数字，找到它在电话按键上对应的所有字母。对于当前数字对应的每个字母，将其添加到之前步骤生成的所有组合中，形成新的组合列表。使用新生成的组合列表替换原来的组合列表。完成所有输入数字的处理后，返回最终的组合列表。
- 时间复杂度：O(3^M×4^N)。M 是对应三个字母的数字个数，N 是对应四个字母的数字个数。
- 空间复杂度：O(3^M×4^N)。一共要生成 3^M×4^N个结果。
- 参考代码：
java版：
class Solution {
private static final String[] MAPPING = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
// 如果输入为空，则返回空的列表
if (digits == null || digits.length() == 0) {
return result;
}
// 初始化结果列表，添加一个空字符串以启动组合过程
result.add("");
for (char digit : digits.toCharArray()) {
// 对于每个数字，找到对应的字母字符串，并与之前的结果组合
// MAPPING[digit - '0']用于直接将数字字符转换为对应的数组索引，并访问该索引位置的元素
result = combine(MAPPING[digit - '0'], result);
}
// 返回所有可能的字母组合
return result;
}
// 为当前数字找到对应的所有字母，并与之前的结果进行组合
private List<String> combine(String letters, List<String> prevResult) {
List<String> newResult = new ArrayList<>();
// 遍历当前数字对应的每个字母
// 例如2对应abc
for (char letter : letters.toCharArray()) {
// 将当前字母与之前的每个组合结果相加
// 就是""+a,""+b,""+c
// 如果下一个是3的话就是def
// a+d,b+d,c+d,a+e,b+e,c+e,a+f,b+f,c+f
for (String str : prevResult) {
newResult.add(str + letter);
}
}
// 返回新的组合结果列表
return newResult;
}
}C++版：
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
// 数字到字母的映射
vector<string> mapping = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
// 初始化结果为包含一个空字符串的列表
vector<string> result{ "" };
//遍历给的数字字符串
for (char digit : digits) {
// 临时列表存储当前迭代的组合结果
vector<string> temp;
// 遍历当前数字对应的所有可能字母
for (char letter : mapping[digit - '0']) {
// 对之前的每个结果字符串
for (const string& combination : result) {
// 添加新字母形成新组合
temp.push_back(combination + letter);
}
}
// 更新结果列表为当前迭代的组合结果
result.swap(temp);
}
return result;
}
};C版：
// 数字到字母的映射关系
char* mapping[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 动态数组结构，用于存储字符串数组
typedef struct {
char** elements; // 指向字符串数组的指针
int size; // 数组中字符串的数量
} DynamicArray;
// 初始化动态数组
void initDynamicArray(DynamicArray* arr) {
arr->elements = NULL;
arr->size = 0;
}
// 向动态数组添加字符串
void addElement(DynamicArray* arr, const char* str) {
arr->size += 1;
arr->elements = (char**)realloc(arr->elements, arr->size * sizeof(char*));
arr->elements[arr->size - 1] = (char*)malloc(strlen(str) + 1);
strcpy(arr->elements[arr->size - 1], str);
}
// 清理动态数组
void freeDynamicArray(DynamicArray* arr) {
for (int i = 0; i < arr->size; i++) {
free(arr->elements[i]);
}
free(arr->elements);
arr->elements = NULL;
arr->size = 0;
}
// 主要的迭代法实现
char** letterCombinations(char* digits, int* returnSize) {
// 如果输入为空字符串，设置returnSize为0，并返回NULL
if (digits == NULL || digits[0] == '\0') {
*returnSize = 0;
return NULL;
}
DynamicArray result;
initDynamicArray(&result);
// 开始时添加一个空字符串
addElement(&result, "");
for (int i = 0; digits[i] != '\0'; i++) {
DynamicArray temp;
initDynamicArray(&temp);
char* letters = mapping[digits[i] - '0']; // 获取当前数字对应的字母
for (int j = 0; letters[j] != '\0'; j++) {
for (int k = 0; k < result.size; k++) {
// 对于result中的每个元素，追加当前字母并添加到temp中
char* newCombination = (char*)malloc(strlen(result.elements[k]) + 2);
sprintf(newCombination, "%s%c", result.elements[k], letters[j]);
addElement(&temp, newCombination);
free(newCombination);
}
}
// 使用temp更新result，并清理temp
freeDynamicArray(&result);
result = temp;
}
*returnSize = result.size;
return result.elements;
}解法三：队列
- 描述：开始时，队列中只有一个空字符串，作为生成字母组合的基础。遍历输入的数字字符串，对于每个数字，按照映射关系找到对应的所有字母。对于当前数字对应的每个字母，从队列中取出前一步骤生成的所有组合（这些组合是基于之前所有数字的），然后将当前字母追加到每个组合后面，生成新的组合。将新生成的组合重新加入队列，为处理下一个数字做准备。当所有数字都处理完毕后，队列中存储的就是所有可能的字母组合。将这些组合从队列中取出，存储到结果数组中。
- 时间复杂度：O(3^M×4^N)。M 是对应三个字母的数字个数，N 是对应四个字母的数字个数。
- 空间复杂度：O(3^M×4^N)。一共要生成 3^M×4^N个结果。
- 参考代码：
java版：
class Solution {
public List<String> letterCombinations(String digits) {
// 创建一个队列来存储所有可能的字母组合
LinkedList<String> combinations = new LinkedList<>();
// 如果输入的数字字符串为空，直接返回空的列表
if (digits.isEmpty())
return combinations;
// 数字到字母的映射
String[] mapping = new String[] {
"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
// 初始时，向队列中添加一个空字符串，作为构建组合的起点
combinations.add("");
// 遍历输入的每个数字，逐个处理
for (int i = 0; i < digits.length(); i++) {
// 将字符转换为数字，以便从映射表中获取对应的字母字符串
int digit = Character.getNumericValue(digits.charAt(i));
// 循环条件确保只处理当前数字生成的组合
// 通过检查队列前端元素的长度与当前处理的数字索引i是否相等来控制循环。
// 当长度不再等于i时，表示当前数字对应的所有可能字母已经处理完毕，循环结束，进入下一个数字的处理。
while (combinations.peek().length() == i) {
// 从队列前端移除元素，这个元素是当前处理步骤的基础组合
String t = combinations.remove();
// 遍历当前数字对应的所有可能字母
for (char c : mapping[digit].toCharArray()) {
// 将当前字母添加到基础组合末尾，并将新组合加入队列末尾
combinations.add(t + c);
}
}
}
// 输入字符串处理完毕，队列中存储了所有可能的字母组合
return combinations;
}
}C++版：
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> result;
if (digits.empty()) return result;
// 数字到字母的映射
vector<string> mapping = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
// 初始化队列并添加一个空字符串作为起始组合
queue<string> q;
q.push("");
// 遍历每个数字字符
for (char digit : digits) {
int n = q.size();
// 获取当前数字对应的所有可能字母
string letters = mapping[digit - '0'];
// 对于队列中的每个现有组合，尝试添加当前数字对应的每个字母
for (int i = 0; i < n; i++) {
// 获取并移除队列前端的组合
string currentCombination = q.front();
q.pop();
// 遍历当前数字对应的每个字母，生成新组合并加入队列
for (char letter : letters) {
q.push(currentCombination + letter);
}
}
}
// 将队列中的所有组合移动到结果向量中
while (!q.empty()) {
result.push_back(q.front());
q.pop();
}
return result;
}
};C版：
// 定义队列节点
typedef struct Node {
char* combination; // 存储当前的字母组合
struct Node* next; // 指向下一个节点
} Node;
// 定义队列结构
typedef struct {
Node* front; // 队列头部
Node* rear; // 队列尾部
int size; // 队列中元素的数量
} Queue;
// 初始化队列
void initQueue(Queue* q) {
q->front = q->rear = NULL;
q->size = 0;
}
// 检查队列是否为空
int isEmpty(Queue* q) {
return q->size == 0;
}
// 入队操作
void enqueue(Queue* q, const char* combination) {
Node* newNode = (Node*)malloc(sizeof(Node));
int len = strlen(combination);
newNode->combination = (char*)malloc(len + 1); // +1 for '\0'
strcpy(newNode->combination, combination);
newNode->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}
// 出队操作
char* dequeue(Queue* q) {
if (isEmpty(q)) {
return NULL;
}
Node* temp = q->front;
char* combination = temp->combination;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp); // 释放出队节点，但不释放字符串，字符串将返回给调用者
q->size--;
return combination;
}
// 电话号码到字母的映射
const char* mapping[] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 主函数，解决电话号码字母组合问题
char** letterCombinations(char* digits, int* returnSize) {
// 如果输入为空字符串，设置returnSize为0，并返回NULL
if (digits == NULL || digits[0] == '\0') {
*returnSize = 0;
return NULL;
}
Queue q;
initQueue(&q);
enqueue(&q, ""); // 初始入队一个空字符串，作为组合的起始点
for (int i = 0; digits[i] != '\0'; i++) {
int digit = digits[i] - '0';
int n = q.size; // 记录当前队列大小，即这一轮需要处理的组合数量
for (int j = 0; j < n; j++) {
char* current = dequeue(&q);
for (int k = 0; mapping[digit][k] != '\0'; k++) {
int currLen = strlen(current);
char* newCombination = (char*)malloc(currLen + 2); // +2: 1 for new char, 1 for '\0'
strcpy(newCombination, current);
newCombination[currLen] = mapping[digit][k];
newCombination[currLen + 1] = '\0';
enqueue(&q, newCombination);
free(newCombination); // 避免内存泄漏
}
free(current); // 避免内存泄漏
}
}
*returnSize = q.size;
char** result = (char**)malloc(q.size * sizeof(char*));
for (int i = 0; i < *returnSize; i++) {
result[i] = dequeue(&q); // 将队列中的组合移动到结果数组中
}
return result;
}