LeetCode 솔루션 분류
[5/9] 17. Letter Combinations of a Phone Number
본문
[LeetCode 시즌 3] 2022년 5월 9일 문제입니다.
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
17. Letter Combinations of a Phone Number
Medium
9855675Add to ListShareGiven 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 digit 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 <= 4
digits[i]
is a digit in the range['2', '9']
.
관련자료
-
링크
댓글 3
austin님의 댓글
- 익명
- 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.5 MB, less than 84.83% of C++ online submissions for Letter Combinations of a Phone Number.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.5 MB, less than 84.83% of C++ online submissions for Letter Combinations of a Phone Number.
class Solution {
public:
vector<string> letterCombinations(string digits) {
const string m[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> ret = {""}, tmp;
for(auto c: digits) {
for(auto &s : ret) for(auto ch : m[c - '2']) tmp.emplace_back(s + ch);
ret = move(tmp);
}
return digits.empty() ? vector<string>{} : ret;
}
};
나무토끼님의 댓글
- 익명
- 작성일
Runtime: 41 ms, faster than 54.53% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.1 MB, less than 31.71% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.1 MB, less than 31.71% of Python3 online submissions for Letter Combinations of a Phone Number.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if len(digits) == 0:
return []
letter_dict = {2:['a','b','c'], 3:['d','e','f'], 4:['g','h','i'], 5:['j','k','l'], 6:['m','n','o'], 7:['p','q','r','s'], 8:['t','u','v'], 9:['w','x','y','z']}
res = []
temp = []
def backtracking(s, idx, cnt, temp):
if cnt == len(digits):
temp_digits = ''.join(temp)
res.append(temp_digits)
return
for l in range(idx, len(s)):
l_dict = letter_dict[int(digits[l])]
for l2 in l_dict:
temp.append(l2)
backtracking(s, l + 1, cnt + 1, temp)
temp.pop()
backtracking(digits, 0, 0, temp)
return res
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.6 MB, less than 60.06% of C++ online submissions for Letter Combinations of a Phone Number.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.6 MB, less than 60.06% of C++ online submissions for Letter Combinations of a Phone Number.
class Solution {
private:
void combination(vector<string> &res, vector<string> &lets, string s) {
int pos = s.size();
if (pos == lets.size()) {
res.push_back(s);
return;
}
for (int i = 0; i < lets[pos].size(); ++i) {
s.push_back(lets[pos][i]);
combination(res, lets, s);
s.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
map<char, string> pad = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
vector<string> lets;
vector<string> res;
for (int i = 0; i < digits.size(); ++i) {
lets.push_back(pad[digits[i]]);
}
if (lets.size() > 0) {
combination(res, lets, "");
}
return res;
}
};