17. Letter Combinations of a Phone Number - medium
문제
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.
제한사항
- Although the above answer is in lexicographical order, your answer could be in any order you want.
입출력 예
1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
풀이
- String,BackTracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
void backTracking(const string& digits, const int& index, const string& now, vector<string>& ans){
// 현재 digits의 index가 digits.size()보다 커지면,
// 현재까지 구성한 문자열을 정답 vector에 저장
if(index > digits.size() - 1){
ans.push_back(now);
return;
}
// 미리 구성한 keypad의 index 계산
// 현재까지 구성한 문자열에 지금 숫자의 keypad에 할당된 모든 새로운 문자 추가
int digitIndex = digits[index] - '0';
for(const auto& i : keypad[digitIndex]){
string nowStr = now;
nowStr.push_back(i);
backTracking(digits, index + 1, nowStr, ans);
}
};
vector<string> letterCombinations(string digits) {
if(digits.size() < 1)
return {};
vector<string> ans;
backTracking(digits, 0, "", ans);
return ans;
}
private:
vector<vector<char>> keypad = { {}, {}, {'a' , 'b', 'c'}, {'d' , 'e', 'f'},
{'g' , 'h', 'i'}, {'j' , 'k', 'l'}, {'m' , 'n', 'o'},
{'p' , 'q', 'r', 's'}, {'t' , 'u', 'v'}, {'w' , 'x', 'y', 'z'}
};
};