프로그래머스 - 모음사전

이 문제(소수 찾기)와 유사하다.
특정 길이가 됐을 때가 아닌 모든 단계의 경우의 수에서, 현재 단계까지 만든 단어를 사용하는 부분이 똑같은데 이것만 알면 간단히 풀 수 있다.

class Solution {
    static String word;
    static String arr = "AEIOU";
    static int answer = 0;
    static int cnt = 0;
    static boolean found = false;
    public int solution(String word) {
        this.word = word;
        bt(0, "");
        return answer;
    }
    static void bt(int index, String madeStr){        
        //다음 단계로 넘온 즉시
        if(!madeStr.equals("")){
            //새 단어가 만들어졌으므로 n번째++
            cnt++;
            if(madeStr.equals(word)){
                //만들어진 단어가 word와 같으면 종료
                answer = cnt;
                found = true;
            }
        }
        //index가 5면 return _단어를 조합해 다섯번째자리까지 만들면 return
        if(index == arr.length()){
            return;
        }
        for(int i = 0; i < arr.length(); i++){
            //이전까지 만든 단어에 다음 알파벳을 더하여, 다음 index로 넘기기
            bt(index+1, madeStr + String.valueOf(arr.charAt(i)));
            //이전 단계에서 단어를 찾았으면 종료 _시간 줄이기 위해
            if(found){
                return;
            }
        }
    }
}