17. Letter Combinations of a Phone Number
給定一個包含數字（從2到9）的字符串，返回該數字可以表示的所有可能的字母組合。答案可以按任意順序返回。
以下是數字到字母的映射（就像電話按鈕上的一樣）。注意，1不對應任何字母。
範例 1：
輸入：digits = "23" 輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
Python
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# Mapping of digits to corresponding letters
phone_map = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
# If the input is empty, return an empty list
if not digits:
return []
# List to store the combinations
result = []
# Helper function to perform backtracking
def backtrack(index: int, path: str):
# If the current path length is equal to the digits length, add to result
if index == len(digits):
result.append(path)
return
# Get the letters that the current digit maps to
possible_letters = phone_map[digits[index]]
# Loop through the letters and backtrack
for letter in possible_letters:
backtrack(index + 1, path + letter)
# Start backtracking from the first digit
backtrack(0, "")
return result
16.52MB, 41ms
C++
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
// Mapping of digits to corresponding letters
unordered_map<char, string> phoneMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
// If the input is empty, return an empty list
if (digits.empty()) {
return {};
}
// List to store the combinations
vector<string> result;
// Helper function to perform backtracking
function<void(int, string)> backtrack = [&](int index, string path) {
// If the current path length is equal to the digits length, add to result
if (index == digits.size()) {
result.push_back(path);
return;
}
// Get the letters that the current digit maps to
string possibleLetters = phoneMap[digits[index]];
// Loop through the letters and backtrack
for (char letter : possibleLetters) {
backtrack(index + 1, path + letter);
}
};
// Start backtracking from the first digit
backtrack(0, "");
return result;
}
};
8.37MB, 0ms
Javascript
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
// Mapping of digits to corresponding letters
const phoneMap = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
};
// If the input is empty, return an empty list
if (!digits) {
return [];
}
// List to store the combinations
const result = [];
// Helper function to perform backtracking
const backtrack = (index, path) => {
// If the current path length is equal to the digits length, add to result
if (index === digits.length) {
result.push(path);
return;
}
// Get the letters that the current digit maps to
const possibleLetters = phoneMap[digits[index]];
// Loop through the letters and backtrack
for (const letter of possibleLetters) {
backtrack(index + 1, path + letter);
}
};
// Start backtracking from the first digit
backtrack(0, '');
return result;
};
48.12MB, 61ms
