原題鏈接🔗：電話號碼的字母組合
難度：中等????
題目
給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。
示例 1：
輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
輸入：digits = “”
輸出：[]
示例 3：
輸入：digits = “2”
輸出：[“a”,“b”,“c”]
提示：
- 0 <= digits.length <= 4
- digits[i] 是范圍 [‘2’, ‘9’] 的一個數字。
題解
- 解題思路：
LeetCode 上的 “電話號碼的字母組合” 問題要求你根據一個數字電話號碼，生成所有的可能的字母組合。在這個問題中，每個數字鍵對應一組字母，例如：
- 2 對應 ‘a’, ‘b’, ‘c’
- 3 對應 ‘d’, ‘e’, ‘f’
- …
解題思路如下：
理解問題：首先，要清楚每個數字鍵對應的字母組合，以及電話號碼可能的組合方式。
回溯法：這是一個典型的回溯問題，我們可以使用回溯法來解決。回溯法是一種通過遞歸來搜索所有可能解的方法。
構建映射：創建一個映射，將每個數字鍵映射到它對應的字母組合。
遞歸生成組合：使用遞歸函數，每次遞歸調用時，嘗試當前數字鍵的所有可能字母，并將其添加到當前的組合中。
回溯：在遞歸過程中，如果當前組合的長度等于電話號碼的長度，說明找到了一個有效的組合，將其添加到結果中。然后回溯，移除當前添加的字母，嘗試下一個字母。
優化：在生成組合的過程中，如果當前數字鍵沒有對應的字母，直接回溯到上一個數字鍵。
下面是這個問題的一般性解題步驟：
- 定義一個映射
digitToChar，將每個數字映射到對應的字母字符串。- 定義一個遞歸函數
backtrack，接收當前的組合current，當前處理的數字索引index，以及電話號碼digits作為參數。- 在
backtrack函數中，如果index等于電話號碼的長度，將當前的組合current添加到結果result中。- 對于當前索引
index，獲取當前數字對應的所有字母，然后對每個字母進行遞歸調用backtrack，并將字母添加到當前組合current中。- 在遞歸調用后，需要回溯，即從
current中移除最后添加的字母。
- c++ demo：
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;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;backtrack(combinations, phoneMap, digits, 0, combination);return combinations;}void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {if (index == digits.length()) {combinations.push_back(combination);}else {char digit = digits[index];const string& letters = phoneMap.at(digit);for (const char& letter : letters) {combination.push_back(letter);backtrack(combinations, phoneMap, digits, index + 1, combination);combination.pop_back();}}}
};int main() {Solution solution;std::string digits = "23";std::vector<std::string> combinations = solution.letterCombinations(digits);for (const std::string& combination : combinations) {std::cout << combination << std::endl;}return 0;
}
- 代碼倉庫地址：letterCombinations
