[Leetcode(릿코드)] 17. Letter Combinations of a Phone Number (Medium, Java)

Question

• 문제 링크 : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

• 분류 : 백크래킹

• 풀이 시간 : 10분

문제 해설

1. 2 ~ 9까지 숫자를 포함하는 문자열이 주어짐
2. 이 숫자를 눌러서 나타낼 수 있는 모든 문자 조합을 반환
   1. 숫자 매핑 문제에 사진 존재
   2. 1은 어떤 문자에도 매핑되지 않음
3. 임의의 순서로 답변 반환

Solution

풀이 접근 방법

1. 나타낼 수 있는 모든 문자의 조합 = 버튼 하나에 3~4가지 문자를 대입할 수 있음 = 백트래킹으로 구현

정답 코드

class Solution {
    public String[] letters = {"", "", "abc", "def", "ghi", "kjl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> result;
    
    public List<String> letterCombinations(String digits) {
        result = new ArrayList<String>();
        
        if (digits.length() > 0) {
            comb(0, new StringBuilder(), digits.toCharArray());
        } 
        return result;
    }
    
    public void comb(int pick, StringBuilder sb, char[] order) {
        // 뽑은 개수 == 문자열의 길이 : 다 뽑읍
        if (pick == order.length) {
            result.add(sb.toString());
            return;
        }
        
        // 해당 번호를 눌렀을 때 입력 가능한 캐릭터 배열 
        char[] charArr = letters[Character.getNumericValue(order[pick])].toCharArray();
      
        // 배열을 돌면서 입력했다가 다시 빼기
        for (int i = 0; i < charArr.length; i++) {
            sb.append(charArr[i]);
            comb(pick + 1, sb, order);
            sb.delete(sb.length() - 1, sb.length());
        }
    }
}