[プログラマー/奥行き、幅優先ナビゲーション(DFS/BFS)/3]ワード変換(JAVA)


ソース:プログラマコードテスト深さ、幅優先ナビゲーション(DFS/BFS)の3番目の問題
( https://programmers.co.kr/learn/courses/30/lessons/43163 )
問題の説明
2つの単語begin、target、単語の集合語があります.次のルールを使用して、beginからtargetに変換する最短変換プロセスを検索します.
一度に1つのアルファベット
  • しか置き換えられません.
  • 個の単語にしか変換できません.
  • たとえば、beginが「hit」、targetが「cog」、単語が「hot」、「dog」、「lot」、「log」、「cog」の場合、「hit」->「hot」->「dog」->「cog」の4つのステップで変換できます.
    2つの単語begin、target、および単語の集約語をパラメータとして指定する場合は、少なくともいくつかのステップを経てbeginをtargetに変換するには、解法関数を記述します.
    せいげんじょうけん
    各単語はアルファベット小文字のみで構成されます.
  • 各単語の長さは3または10を超えず、すべての単語の長さは同じである.
  • 個の単語は3個または50個以上の単語があり、重複する単語はありません.
  • beginとtargetは異なります.
  • が変換できない場合は0を返します.
  • 解答方法
  • を巡回すると、単語配列に近いかどうかがアクセス配列として定義され、falseに初期化される.
  • によって与えられたbeginから、この字が変換可能なすべての単語が受信される.
  • 変換可能な単語を複文に変換し、ここで再帰関数を実行する.
  • 再帰関数を実行すると、変換可能な単語にtargetがある場合、以前に実行したカウントを終了して返します.
  • ソースコード
    import java.util.*;
    
    class Solution {
        private int answerCnt = 0;
        private boolean isFound = false;
        private String target = null;
        
        public int solution(String begin, String target, String[] words) {
            List<String> visited = new ArrayList<String>();
            this.target = target;
            List<String> newWords = Arrays.asList(words);
            search(begin,newWords,visited,1);
            return answerCnt;
        }
        private void search(String str, List<String> words, List<String> visited, int cnt) {
            if ( isFound ) return;
            visited.add(str);
            List<String> convertableWords = getConvertableWords(str,words,visited);
            if ( convertableWords.size() < 1 ) return;
            if ( convertableWords.contains(target) ) {
                answerCnt = cnt;
                isFound = true;
                return;
            }
            for ( String word : convertableWords ) {
                search(word,words,new ArrayList<>(visited),cnt+1);
            }
        }
        private List<String> getConvertableWords(String str,List<String> words,List<String> visited) {
            List<String> convertableWords = new ArrayList<String>();
            for ( String word : words ) {
                if ( visited.contains(word) ) continue;
                if ( !isConvertable(str,word) ) continue;
                convertableWords.add(word);
            }
            return convertableWords;
        }
    
        private boolean isConvertable(String str, String target) {
            char[] strChars = str.toCharArray();
            char[] targetChars = target.toCharArray();
            int cnt = 0;
            for ( int i = 0; i < strChars.length; i++ ) {
                if ( strChars[i] == targetChars[i] ) {
                    cnt++;
                }
            }
            return cnt == strChars.length - 1 ? true : false;
        }
    }
    ポスト
    この間ずっと探索問題が難しいと思っていたが、今はある程度の問題が解決できる自信がある.