리트코드 - Letter Combinations of a Phone Number

리트코드 - Letter Combinations of a Phone Number

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

 

문제 설명

주어진 문자열이 2에서 9까지의 숫자를 포함하고 있을 때, 이 숫자가 나타낼 수 있는 모든 가능한 문자 조합을 반환합니다. 답은 어떤 순서로든 반환될 수 있습니다.

숫자와 문자의 매핑은 아래와 같이 전화 버튼과 같습니다. 1은 어떤 문자에도 매핑되지 않는다는 점을 유의하세요.

 

의사코드

# 전화 번호 패드에 해당하는 문자열을 저장하는 배열 phoneLetters = ["", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] 함수 letterCombinations(digits)     answer = new ArrayList     if (digits.length() == 0)         answer 리턴         combine(answer, digits, "", 0)     answer 리턴 함수 combine(answer, digits, cur, index)     # 현재 인덱스가 digits의 길이와 같다면, 하나의 조합이 완성된 것이므로 결과에 추가     if (digits.length == index)         answer.add(cur)         return     # 현재 숫자에 해당하는 문자열 가져오기     letters = phoneLetters[digits.charAt(index) - '1']     # 현재 문자열의 각 문자에 대해 재귀적으로 조합을 이어감     for (letters 배열 한글자씩 char 순회)         combine(answer, digits, cur + letter, index + 1)

 

풀이코드

class Solution {
    public static String[] phoneLetters = {"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> answer = new ArrayList<>();
        if (digits.length() == 0) { 
            return answer;
        }
        combine(answer, digits, "", 0);
        return answer;
    }

    public void combine(List<String> answer, String digits, String cur, int index) {
        if (index == digits.length()) {
            answer.add(cur);
            return;
        }

        String letters = phoneLetters[digits.charAt(index) - '1'];

        for (char letter : letters.toCharArray()) {
            combine(answer, digits, cur + letter, index + 1);
        }
    }
}

코드설명

이전 조합문제와 비슷한 문제이다.

여러 방법이 있지만 배열을 통해 먼저 static으로 문자열 배열을 만들어서 구현했다.

 

이전에는 숫자 하나씩 조합하는 경우였다면 이번에는 하나의 숫자에 여러 개의 문자열이 들어있는게 큰 차이점이다.

 

앞선 문제에서는 배열에 하나씩 넣고 뺐고를 반복했다면, 이번에는 파라미터에 cur + letter를 통해 cur가 변경되지 않도록 하였다.

String은 불변하는 객체이므로 cur + letter를 통해 전달한 새로운 String이 아래 메소드에 전달된다.

for (char letter : letters.toCharArray()) {
    combine(answer, digits, cur + letter, index + 1);
}

 

따라서 메소드를 빠져나오면 cur는 원래의 값을 가지고 있으므로 letter에 대해 별도의 삭제가 없어도 다음 letter를 쉽게 추가할 수 있다.

 

재귀적인 부분에서는 위와같은 차이가 있고, letters를 빼내기 위해 String letters = phoneLetters[digits.charAt(index) - '1']을 사용했다.

배열은 0부터 시작하므로 마이너스 '1'을 통해 숫자에 해당하는 문자열을 가져오게 된다.

 

예를 들어 주어진 digits이 "23"인 경우 digits.charAt(index)에서 index가 0이면 '2'가 나오고, '2'-'1' 을 통해  phoneLetters[1] 을 하여 "abc"를 가져올 수 있게 된다.

 

시간복잡도 - O(4^n) (n은 길이, 최악의 경우 문자가 4개인 7,9로만 n개 이루어진 digits)

공간복잡도 - O(4^n) (위와 상동)

 

정리

재귀를 이용한 조합 구현2