본문 바로가기

LeetCode

[LeetCode] - 17. Letter Combinations of a Phone Number

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Letter Combinations of a Phone Number" 문제입니다.

--> https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

 

문제 : 

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 <= 4
  • digits[i] is a digit in the range ['2', '9'].

이 문제는 주어진 숫자 문자열을 사용하여 전화기 키패드의 문자 조합을 모두 반환하는 문제입니다. 예를 들어, 입력이 "23"이면 가능한 문자 조합은 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]입니다. 문자열이 비어있으면 빈 배열을 반환하고, 숫자가 하나인 경우 해당 숫자에 매핑된 문자를 모두 반환합니다.

 

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<String, List<String>> digitsMap = new HashMap<>();
        digitsMap.put("2", Arrays.asList("a", "b", "c"));
        digitsMap.put("3", Arrays.asList("d", "e", "f"));
        digitsMap.put("4", Arrays.asList("g", "h", "i"));
        digitsMap.put("5", Arrays.asList("j", "k", "l"));
        digitsMap.put("6", Arrays.asList("m", "n", "o"));
        digitsMap.put("7", Arrays.asList("p", "q", "r", "s"));
        digitsMap.put("8", Arrays.asList("t", "u", "v"));
        digitsMap.put("9", Arrays.asList("w", "x", "y", "z"));

        List<String> res = new ArrayList<>();

        if (digits.length() == 0) return res; // Return empty list for empty input

        letterCombinationsHelper(digitsMap, digits, 0, "", res);
        
        return res;
    }

    private static void letterCombinationsHelper(Map<String, List<String>> digitsMap, String digits, int index, String comb, List<String> res) {
        if (index == digits.length()) {
            res.add(comb);
            return;
        }
        String digit = String.valueOf(digits.charAt(index));
        if (digitsMap.containsKey(digit)) {
            for (String letter : digitsMap.get(digit)) {
                letterCombinationsHelper(digitsMap, digits, index + 1, comb + letter, res);
            }
        }
    }
}

 

이 코드는 딱 한 눈에 봐도 아주 효율적이진 못해 보입니다. 아무래도 초반에 일일이 매핑하는 게 시간을 많이 까먹게 생겼죠. 그래도 제 코드를 설명드리겠습니다 : 

  1. 맵 초기화:
    • 전화기 키패드의 숫자와 문자들을 매핑하는 맵을 초기화합니다.
  2. 결과 리스트 초기화 및 입력 검증:
    • 결과를 저장할 리스트를 초기화합니다.
    • 입력 문자열이 비어있으면 빈 리스트를 반환합니다.
  3. 재귀 함수 호출:
    • 재귀 함수를 호출하여 가능한 모든 문자 조합을 생성합니다.
  4. 재귀 함수 정의:
    • 현재 인덱스가 입력 문자열의 길이와 같으면 현재 조합을 결과 리스트에 추가합니다.
    • 현재 숫자의 문자를 가져와서 각 문자를 순회하면서 재귀적으로 다음 조합을 생성합니다.

시간 및 공간 복잡도:

  1. 시간 복잡도:
    • 각 숫자가 최대 4개의 문자로 매핑되므로, 모든 조합을 생성하는 시간 복잡도는 O(4^n)입니다. 여기서 n은 입력 문자열의 길이입니다.
  2. 공간 복잡도:
    • 재귀 호출 스택의 깊이는 입력 문자열의 길이 n에 비례합니다.
    • 결과 리스트의 크기는 생성된 모든 조합의 수에 비례합니다.
    • 따라서 공간 복잡도는 O(n)입니다.

 


그래서 제가 다른 유저들의 모범답안을 하나 인용해 오겠습니다 : 

class Solution {
    List<String> res = null;
    String [] strMap = {"0","1","abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if(digits.length() == 0){
            return res;
        }
        dfs(0,digits,new StringBuilder());
        return res;
    }

    void dfs(int length ,String digits,StringBuilder temp){

        if(length == digits.length()){
            res.add(temp.toString());
            return; 
        }

        char ch = digits.charAt(length);
        String str = strMap[ch -'0'];

        for(char c:str.toCharArray()){
            temp.append(c);
            dfs(length+1,digits,temp);
            temp.deleteCharAt(temp.length()-1);
        }

    }
}

 

백 트래킹을 잘 이용한 코드입니다. 


내 코드와 다른 유저의 코드 Runtime 결과