[Lv.2] 모음 사전 : Java

 

프로그래머스

 

만들 수 있는 문자열이 몇 개 없으니까 다 만들어보기

DFS + 백트래킹 > 원하는 단어랑 일치하면 cnt 리턴

 

이미 찾은 경우 재귀 멈추는 flag 유의하기 : 조기 중단해야 하는 경우

class Solution {
    static final char[] a = {'A', 'E', 'I', 'O', 'U'};
    static String word;
    static int result = 0;
    
    public int solution(String word) {
        // DFS 백트래킹 이용 > AEIOU 순으로 깊이를 1~5로 확장하면서 단어 하나씩 만들때마다 카운트 > word랑 같으면 result 반환
        
        this.word = word;
        dfs("");    // 빈 문자열에서 시작
        return result;
        
    }
    
    static boolean flag = false;
    public static void dfs(String s){
        if(flag) return;    // 이미 찾았으면 중단
        if(s.length() == 5) return; // 최대 길이 5
        
        for(char c : a){
            String next = s + c;
            result++;
            if(word.equals(next)){
                // 원하는 단어랑 같은 경우
                flag = true;
                return;
            }
            dfs(next);
            if(flag) return;
        }
    }
}