LeetCode 솔루션

[5/9] 17. Letter Combinations of a Phone Number

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.08 20:07

16,052 조회
3 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

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

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

#LeetCode, #Amazon, #Microsoft, #Facebook, #Uber, #Apple, #Google, #Bloomberg, #Epic Systems, #Swiggy, #Twitter, #Oracle, #Hash Table, #String, #Backtracking

링크

https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 5825 회 연결

익명
작성일 2022.05.08 22:39

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;        
    }
};

익명
작성일 2022.05.09 16:15

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

[code=python]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[/code]

익명
작성일 2022.05.09 23:00

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;
    }
};

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.
[code=C++]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;
    }
};[/code]