(level1) 옹알이 (2)

https://school.programmers.co.kr/learn/courses/30/lessons/133499

연속으로는 발음할 수 없고, 패턴에 따라서 달리 매칭될 수 있을 거로 생각해서
DFS로 풀었다.

그러면서 이거 왜 레벨 1짜리 문제지.. 하고 생각했는데
다른 사람 풀이 보니까 그냥 연속단어 뭉치 (예를 들면 "ayaaya")를 허용하지 않고
이후에 각 단어들을 치환해서 마지막에 isEmpty() 체크하더라..

똑똑하네..

class Solution {
    private String[] canSay = new String[] {
        "aya",
        "ye",
        "woo",
        "ma"
    };
    public int solution(String[] babbling) {
        int answer = 0;
        
        for (String b : babbling) {
            if (dfs(b, 0, -1)) {
                answer++;
            }
        }
        return answer;
    }
    
    private boolean dfs(String bab, int index, int prev) {
        if (index == bab.length()) {
            return true;
        }
        
        for (int i=0; i<canSay.length; i++) {
            if (i == prev) {
                continue;
            }
            
            String word = canSay[i];
            if (bab.startsWith(word, index)) {
                if (dfs(bab, index + word.length(), i)) {
                    return true;
                }
            }
        }
        return false;
    }
}