엔지니어 게시판
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 ListShare

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

200px-Telephone-keypad2.svg.png

 

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.
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.

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.
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;
    }
};
전체 396 / 8 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 147 명
  • 오늘 방문자 4,138 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,048 명
알림 0