プログラマdfs bfs単語変換

質問リンク

問題の説明

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に変換するには、解法関数を記述します.

に答える

これは設計問題解決方式の論理に基づいて得られた問題である.しかし、それを実現する時、いくつかの小さな間違いがあって、私に多くの苦労をさせました.dfs方式で解読したのは,単語変換時に1文字しか変換できないため,変換と同時にターゲット文字を達成するために垂直方向に新しい状況の数を増やしたため,直感である.一般的なdfsのようにboolean[]visitを宣言し、すでにアクセスしたノードがアクセスされなくなったが、これは単純な接続ではなく、少数の場合に最小値のdfsを見つけるためにvisit[i]を再初期化した.

コード#コード#

import java.util.*;
class Solution {
   static boolean[] visit;
   static int c;
   public int solution(String begin, String target, String[] words) {
       c = 50;
       int len = words.length;
       
       visit = new boolean[len];
       dfs(begin, target, words, 0);
       return  c==50? 0: c;
       
   }
   static void dfs(String begin, String target, String[] words, int count){
       if(begin.equals(target)) {
          c= Math.min(c, count);
           System.out.print(c);
       }
       for(int i=0;i<words.length;i++){
           if(checkDiff(begin, words[i])&&!visit[i]){
               visit[i]=true;
               dfs(words[i],target, words, count+1);
               visit[i]=false;
           }
       }
   }
   static boolean checkDiff(String first, String second){
       int diff =0;
       boolean check= false;
       for(int i=0; i< first.length();i++){
           if(first.charAt(i)==second.charAt(i)) {
               diff++;
           }
       }
       if(diff==first.length()-1) check =true;
       return check;
   }
}