[LeetCode- Ch9. 백트래킹] 4. 핸드폰 숫자의 문자 조합

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

Letter Combinations of a Phone Number - LeetCode

 

1. DFS 이용

2. 이중 for문 이용

: 뒤부터 시작

 

 

class Solution {
    static int[] digitarr;
    static int tmp=0;
    public List<String> letterCombinations(String digits) {
        //숫자에 해당하는 문자가 나올 수 있는 총 경우의 수 구하기
        List<String> result = new ArrayList<String>();
        if(digits.length()==0 || digits==null) return result;
        String digitletter[] = { "0", ",", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        digitarr = new int[digits.length()];
        for(int i=0; i<digits.length(); i++){
            tmp=Character.getNumericValue(digits.charAt(i));
            digitarr[i]=tmp;
        }
        DFS(0, result,digits,0, digitletter,"");
        
        return result;
    }
    private void DFS(int n, List<String> result,String digits,int m, String[] digitletter, String str){
        if(str.length()==digits.length()){
            result.add(str);
        }
        if(n>=digitarr.length||m>=digitletter[digitarr[n]].length()) return;
        
        for(int i=m;i<digitletter[digitarr[n]].length();i++){
            char c =digitletter[digitarr[n]].charAt(i);
            str+=digitletter[digitarr[n]].charAt(i);
            System.out.println("i와 str: "+i+" "+str);
            
            DFS(n+1, result,digits,m, digitletter,str);
            str=str.substring(0, str.length()-1);                   
        }
     }
}

 

+) 세련된 풀이

class Solution {
    public List<String> letterCombinations(String digits) {
        //숫자에 해당하는 문자가 나올 수 있는 총 경우의 수 구하기
        String digitletter[] = {"",",", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<String>();
        if(digits.length()==0 || digits==null) return result;
        result.add("");
        
        for(int i=0; i<digits.length(); i++){
            //char를 int로 형변환
            result=combine(result, digitletter[digits.charAt(i)-'0']);
        }
        
        return result;

    }
    private List<String> combine(List<String> firstList, String digit){
        List<String> result = new ArrayList<>();
        for(int i=0;i<digit.length(); i++){
            for(String firstStr : firstList) result.add(firstStr+digit.charAt(i));
        }
        return result;
    }
}