HackMD
【LeetCode】 17. Letter Combinations of a Phone Number
Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
給一串包含數字 2-9 的字串，回傳所有可能出現的字母組合。
每個數字到字母的對應表在下方(就像手機按鈕一樣)，記住1沒有對應到任何字母。
注意：
雖然範例中的答案有按字典排序，但實際上你可以用任何順序。
Example:
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Solution
- 用一個
vector<string>當作對應表，1的部分放入空字串就可以了。 - 每次放入一個字母，用迴圈去放下一種字母(同一個按鈕)；用遞迴去放下一個字母(下一個按鈕)。
- 注意如果輸入是空的，不可回傳任何空字串。
Code
class Solution {
public:
void addLetter(string dights, string word, vector<string>& ans)
{
vector<string> btn = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
if(dights.empty())
{
if(!word.empty())
ans.push_back(word);
}
else
{
for(int i = 0; i < btn[dights[0] - '1'].size(); i++)
{
addLetter(dights.substr(1), word + btn[dights[0] - '1'][i], ans);
}
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
addLetter(digits, string(), ans);
return ans;
}
};
