[LeetCode] 17. Letter Combinations of a Phone Number - 깊이우선탐색(DFS) + 구현(Implementation) JAVA

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

코드설명

깊이우선탐색(DFS) + 구현(Implementation) 을 활용합니다.

 

먼저 number 배열에 각 전화번호의 정보를 넣습니다.

그리고 DFS로 전화번호 누른 칸의 각 모든 조합을 만들면 되겠지요.

StringBuilder를 활용하여 문자열 더하기의 시간을 줄여주는것이 중요합니다.

코드

import java.util.*;
 
class Solution {
    String[][] number = new String[][] {
        {"0"},
        {"0"},
        {"a","b","c"},
        {"d","e","f"},
        {"g","h","i"},
        {"j","k","l"},
        {"m","n","o"},
        {"p","q","r","s"},
        {"t","u","v"},
        {"w","x","y","z"}
    };
    List<String> answer = new ArrayList<String>();
    String Digits;
    String[] split;
    public List<String> letterCombinations(String digits) {
        Digits = digits;
        System.out.print(" "+number.length);
        for(int i=0; i<number.length; i++){
            for(int j=0; j<number[i].length; j++){
                System.out.print(number[i][j]+" ");
            }
        }   
        if(digits.length() == 0) return new ArrayList<String>();
 
        split = digits.split("");
        int firstNum = Integer.parseInt(split[0]);
        for(int i=0; i<number[firstNum].length; i++){
            StringBuilder sb = new StringBuilder();
            sb.append(number[firstNum][i]);
            DFS(1, sb);
        }
        return answer;
    }
 
    void DFS(int level, StringBuilder str){
        if(level == Digits.length()){
            answer.add(str.toString());
            return ;
        }
 
        int idx = Integer.parseInt(split[level]);
        for(int i=0; i<number[idx].length; i++){
            StringBuilder newStr = new StringBuilder(str.toString());
            DFS(level + 1, newStr.append(number[idx][i]));
        }
    }
}