17. Letter Combinations of a Phone Number
Đề Bài
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(V+E)
💾 Không gian
O(V)
Lời Giải
C++
0017-letter-combinations-of-a-phone-number.cpp
class Solution {
private:
vector<string> ans;
int n;
vector<string> letters;
string digits;
public:
void backTracking(int i, string path) {
if (path.size() == n) {
ans.push_back(path);
return;
}
for (char c : letters[digits[i] - '0' - 2]) {
backTracking(i + 1, path + c);
}
}
vector<string> letterCombinations(string digits) {
this-> n = digits.size();
if (n == 0) {
return {};
}
int step = 3;
char chr = 'a';
for (int i = 2; i <= 9; ++i) {
if (i == 7 or i == 9) {
step = 4;
}
else {
step = 3;
}
string letter;
for (int j = 0; j < step; ++j) {
letter += chr;
chr += 1;
}
letters.push_back(letter);
}
this->digits = digits;
backTracking(0, "");
return ans;
}
};
Python
0017-letter-combinations-of-a-phone-number.py
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
n = len(digits)
d = dict()
c = 'a'
step = 3
for i in range(2, 10):
string = ""
if i == 7 or i == 9:
step = 4
else:
step = 3
for _ in range(step):
string += c
c = chr(ord(c) + 1)
d[str(i)] = string
self.ans = []
def dfs(i, path):
if i == n:
self.ans.append(path)
return
for c in d[digits[i]]:
dfs(i + 1, path + c)
dfs(0, "")
return self.ans