第十七题：电话号码的字母组合

embedded/2024/10/22 15:32:05/

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有可能的由它组成的字母组合。你可以假设输入字符串至少包含一个数字，并且不超过3位数字。

实现思路

使用哈希表或数组存储每个数字对应的字符，然后通过递归或迭代的方式生成所有可能的组合。如果字符串长度为n，则可以看作是n层循环，每层循环可以选择对应数字的所有字符之一。

算法实现

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>void backtrack(char *digits, int pos, char *combination, int *resultLength, char **result) {static const char *table[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};if (pos == strlen(digits)) {result[*resultLength] = malloc(strlen(combination) + 1);strcpy(result[*resultLength], combination);(*resultLength)++;} else {for (int i = 0; table[digits[pos] - '0'][i]; ++i) {combination[pos] = table[digits[pos] - '0'][i];backtrack(digits, pos + 1, combination, resultLength, result);}}
}int* letterCombinations(char *digits, int *returnSize) {if (!strlen(digits)) return NULL;int resultLength = 0;char *combination[100] = {0};*returnSize = 0;backtrack(digits, 0, (char[5]){0}, &resultLength, combination);int *result = malloc(resultLength * sizeof(int));for (int i = 0; i < resultLength; ++i) {result[i] = (int)combination[i];}return result;
}

Python实现

python">class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return []phoneMap = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}def backtrack(combination, next_digits):if not next_digits:combinations.append(combination)else:for letter in phoneMap[next_digits[0]]:backtrack(combination + letter, next_digits[1:])combinations = []backtrack("", digits)return combinations

Java实现

java">import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Solution {public List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<>();if (digits.length() == 0) {return combinations;}Map<Character, String> phoneMap = new HashMap<>();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");backtrack(combinations, phoneMap, digits, 0, new StringBuilder());return combinations;}private void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuilder combination) {if (index == digits.length()) {combinations.add(combination.toString());} else {String letters = phoneMap.get(digits.charAt(index));for (int i = 0; i < letters.length(); i++) {combination.append(letters.charAt(i));backtrack(combinations, phoneMap, digits, index + 1, combination);combination.deleteCharAt(index);}}}
}