ワードチェンジ

質問する

2つの単語begin、target、および単語の集合語がある場合
begin = "hit"
target = "cog"
words = ["hot","dot","dog","lot","log","cog"]
"hit"-> "hot"-> "dot"-> "dog"-> "cog"
したがって,beginからtargetに変換する最短変換プロセスを探すには,最小のステップを探す必要がある.
(すべての単語の長さは同じで、変換方法がない場合は0を返します.)

に近づく

見るからにDFSで解決しようと思った.どうせ底をひっくり返さなければならないので、別の前処理はしていません.

コード#コード#

class Solution {
    String target;
    String[] words; 
    boolean[] visited; // 단어 방문 여부
    int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        this.words = words;
        this.target = target;
        visited = new boolean[words.length];
        
        dfs(begin, 0);
        return answer;
    }
    
    public void dfs(String str, int cnt) {
        if (str.equals(target) && (answer == 0 || answer > cnt)) {
            answer = cnt;
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                
                String word = words[i];
                int diff = 0; // 글자 차이
            
                for (int j = 0; j < word.length(); j++) {
                    if (str.charAt(j) != word.charAt(j)) {
                        diff++;
                    
                        if (diff >= 2) {
                            break;
                        }
                    }
                
                    if (j == word.length() - 1 && diff == 1) {
                        dfs(word, cnt + 1);
                    }
                }
                
                visited[i] = false;
            }
        }
    }
}

忘れないようにコメントを添付します

DFSの問題を解くと、アクセスした頂点に再アクセスすると無限ループが発生します.
特定の頂点にアクセスしたかどうかを確認することを忘れないでください.

現在の頂点に隣接するすべての点を検索した場合、自分の頂点へのアクセスを未アクセスに解除する必要があります.
△本人の頂点は、後で他の頂点から隣接する頂点になる可能性があるからです.