[Grind75-LeetCode] Letter Combinations of a Phone Number JAVA

반응형

728x90

[Grind75-LeetCode] Letter Combinations of a Phone Number - Medium

---

접근

• dfs

---

풀이

휴대폰 자판에 있는 알파벳을 가지고 나올 수 있는 모든 조합을 구하는 문제이다. 입력으로 여러 개의 숫자가 문자열로 주어지고 해당 숫자칸에 있는 알파벳들의 조합을 구해야 한다. 문자열이 "23"으로 주어졌을 때 2에 해당하는 a, b, c와 3에 해당하는 d, e, f를 조합하는데 각각 번호의 알파벳을 한 개씩 사용해서 조합을 만들어야 한다. 즉 2번과 3번의 알파벳이 한 개씩 사용된 ad, ae, af는 가능하지만 각 번호의 알파벳을 두 번 사용한 ab, de 같은 경우는 불가능하다. 

    private static final String[] DIGITS_MAP = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

미리 번호에 매핑되는 알파벳들을 배열로 만들어뒀다. 0번과 1번은 문자가  존재하지 않아 빈 문자열로 채우고 나머지는 번호에 맞는 알파벳을 채웠다. 

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

        if (digits.isEmpty()) {
            return result;
        }

        dfs(result, new StringBuilder(), digits, 0);
        return result;

    }

입력 문자가 비어있을수도 있기 때문에 비었다면 빈 배열을 반환해 처리를 끝낸다. 문자가 있는 경우 dfs를 사용해 조합을 만들어 준다. StringBuilder를 사용해 주었는데 String 객체는 기본적으로 불변 객체로 + 연산 시 새로운 String 객체를 생성하여 해당 값이 할당이 되는 구조이다. 이번 문제에선 많은 문자열 + 연산이 일어나 수많은 String 객체 생성으로 인한 오버헤드를 줄이기 위해 StringBuilder를 사용한다.

    private void dfs(List<String> result, StringBuilder current, String digits, int index) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        String letters = DIGITS_MAP[digits.charAt(index) - '0'];

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

이전에 풀었던 Subsets 문제와 유사한 풀이이다. 현재 조합이 digits의 길이가 되면 결과에 추가한다. digits의 길이가 되었다는 것은 입력으로 줬던 모든 숫자에 있는 알파벳을 한  개씩 더했다는 뜻이다. 조합을 만드는 과정에서 볼 수 있듯이 index 값을 통해 digits에 있는 숫자로부터 알파벳을 한 개씩 더하며 진행하게 되고 마지막 문자를 제거하여 다른 조합을 다시 탐색할 수 있게 해 준다.  

---

전체 코드

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

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

        if (digits.isEmpty()) {
            return result;
        }

        dfs(result, new StringBuilder(), digits, 0);
        return result;

    }

    private void dfs(List<String> result, StringBuilder current, String digits, int index) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        String letters = DIGITS_MAP[digits.charAt(index) - '0'];

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