'leetcode 17번 답변'에 해당되는 글 1건

문제 : 

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

2-9까지 숫자의 조합이 주어졌을 때, 해당 숫자가 나타낼 수 있는 알파벳의 모든 조합을 구하는 문제이다.

처음부터 자료구조를 HashMap을 사용하기로 생각을 했으나, 어떻게 해야 주어진 문자열 digits.lentgh에 맞춰 반복문을 쓸까 고민을 했다.

그러다가 문득 모든 가능한 경우의 수를 탐색하면서 조건을 만족하는 해를 찾는  백트랙킹(backtracking) 알고리즘이 생각이 났다.

구현 방법이 내가 기억하는 게 맞다면 이런 식으로 구현이 되는데

for(선택지)
 상태 변경
 재귀호출(변경된 상태)
 상태 복귀

긴가민가하여 조금 헤맸다.

우선 내 풀이는 이렇다.

주어진 메인메서드의 리턴값이 List <String>이니 

결과를 리턴해줄 리스트 result를 선언해 준다.

그리고 digitis이 공백일 경우 result를 바로 리턴해 준다.

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

if(digits == null || digits.length()==0){
    return result;
}

이후 각 숫자들이 나타낼 수 있는 알파벳 조합을 저장하기 위해 Map <Character, String>을 생성해 주었다.

Map의 Key타입을 Character로 지정해 준 이유는 digits문자열을 문자 배열(char)로 전환하여 비교할 예정이기 때문이다. 

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

마지막으로 백트랙킹을 만들어 주겠다.

매개변수로는

1. 문자열 digits,

2. 몇 번째 조합인지 체크하는 인덱스 index,

3. 조합을 저장할 StringBuilder,

4. 최종 조합을 저장할 리스트 result,

5. 그리고 각 숫자의 알파벳을 가지고 있는 map이다.

주어진 문자열 digits이 "23"일 경우 나올 수 있는 알파벳 조합의  digits의 길이와 동일한 2이다.

예)

'2' = "abc"

'3' = "def"

2와 3의 모든 조합 :ad, ae, af, bd, be, bf, cd, ce, cf

백트래킹을 재귀적으로 호출하여 탐색할 때, 최대 탐색할 수 있는 깊이를 지정하지 않으면 StackOverFlow가 발생한다.

몇 번째 조합인지 체크(깊이 체크)하는 index가 digits의 길이와 같을 경우 return 하도록 해줬다.

그리고 return 할 때, Stringbuilder는 모든 조합을 탐색한 상태이기 때문에 result에 더 해주도록 한다.

digits가 "23"일 때 아래의 코드는 다음과 같이 작동한다.

    public void backTrack(String digits, int index, StringBuilder comb, 
                          List<String> result, Map<Character, String> map){

        if(index == digits.length()){ // 인덱스의 값이 digits의 길이와 같으면
            result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 더해주고
            return; // return한다.
        }

        String letters = map.get(digits.charAt(index)); // map에 저장된 각 숫자의 알파벳을 저장
		
        // letters에 있는 문자를 하나씩 꺼내온다.
        for(char letter : letters.toCharArray()){
            comb.append(letter); // 꺼내온 문자를 StringBuilder comb에 저장하고
            backTrack(digits, index+1, comb, result, map); // 재귀적으로 조합 탐색
            comb.deleteCharAt(comb.length()-1); // 재귀호출이 끝나면 stringBuilder를 비워준다.
        }
    }

1. backTrack  첫 호출

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(0));  

map에서 '2'의 값 "abc"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'a', 'b', 'c'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // 우선 a를 StringBuilder comb에 입력하고

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 0+1, comb, result, map);  // backTrack에 a 다음에 올 문자 조합을 찾는다.

2. backTrack 두 번째 호출

if(index == digits.length()) // index의 크기가 digits의 길이와 동일하지 않으니 넘어간다.

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(1));  

map에서 '3'의 값 "def"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'d', 'e', 'f'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // comb에 들어있던 a와  d를 더하여 ad를 만든다.

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 1+1, comb, result, map);  // backTrack에 ad 다음에 올 문자 조합을 찾는다.

3. backTrack 세 번째 호출

if(index == digits.length()) //  2==2로 index의 크기가 digits의 길이와 동일하니 

result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 comb에 저장된 문자열 ab를 넣어주고
 return;                                    // return 한다.

4. backTrack 두 번째 호출로 복귀

위와 같이 반복하여 a의 모든 결과를 탐색하여 첫 번째 backTrack으로 돌아오면 

comb에 들어가 있던 a를 comb.deleteCharAt(comb.length()-1)를 통해 최종적으로 제거해 주고 

b와 c의 조합도 탐색하고 종료한다.

전체 코드는 다음과 같다. 

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if(digits == null || digits.length()==0){
            return result;
        }

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

        backTrack(digits, 0, new StringBuilder(), result, map);

        return result;
    }

    public void backTrack(String digits, int index, StringBuilder comb, List<String> result, Map<Character, String> map){

        if(index == digits.length()){
            result.add(comb.toString());
            return;
        }

        String letters = map.get(digits.charAt(index));

        for(char letter : letters.toCharArray()){
            comb.append(letter);
            backTrack(digits, index+1, comb, result, map);
            comb.deleteCharAt(comb.length()-1);
        }
    }
}