Today I Learned

오늘은 leetcode로 돌아가서 medium 단계 문제를 풀었다.

17. 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
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

풀이 과정

• 그냥 for문으로 구현하는 것 보다 더 효율적으로 만들기 위해 백트래킹으로 구성해서 문제를 풀어봤다.

1. 입력 유효성 체크를 먼저 해준 뒤, String 배열로 인덱스에 번호를, 원소로 문자열을 할당해 놓았다.

2. 재귀를 돌릴 거기 때문에 새로 메서드를 하나 만든다. 답변이 저장될 list, digits, letters, 인덱스값, Stringbuilder를 매개변수로 한다.

3. 현재 인덱스가 숫자 문자열의 길이와 같으면 조합을 결과 리스트에 추가하고 종료한다.

4. 위의 조건이 아니면 현재 숫자에 해당하는 문자열을 가져온다. digit - '0'으로 char를 int로 바꾼다.

5. 각 문자에 대해 재귀적으로 호출하여 조합을 완성한다.

결과

• 시간복잡도 상으로 아주 효율적인 코드가 되었다.
  

Java 코드

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        if(digits.length() == 0) return answer;

        String[] letters = {
            "", "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };

        doComb(answer, digits, letters, 0, new StringBuilder());
        return answer;
    }

    public void doComb(List<String> answer, String digits, String[] letters, int index, StringBuilder comb){
        if (index == digits.length()){
            answer.add(comb.toString());
            return;
        }
        char digit = digits.charAt(index);
        String letter = letters[digit - '0'];

        for (int i = 0; i < letter.length(); i++) {
            comb.append(letter.charAt(i));
            doComb(answer, digits, letters, index + 1, comb);
            comb.deleteCharAt(comb.length() - 1);
        }

    }

}