[プログラマー/奥行き、幅優先ナビゲーション(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がある場合、以前に実行したカウントを終了して返します. ソースコード
この間ずっと探索問題が難しいと思っていたが、今はある程度の問題が解決できる自信がある.
( https://programmers.co.kr/learn/courses/30/lessons/43163 )
問題の説明
2つの単語begin、target、単語の集合語があります.次のルールを使用して、beginからtargetに変換する最短変換プロセスを検索します.
一度に1つのアルファベット
2つの単語begin、target、および単語の集約語をパラメータとして指定する場合は、少なくともいくつかのステップを経て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;
}
}
ポストこの間ずっと探索問題が難しいと思っていたが、今はある程度の問題が解決できる自信がある.
Reference
この問題について([プログラマー/奥行き、幅優先ナビゲーション(DFS/BFS)/3]ワード変換(JAVA)), 我々は、より多くの情報をここで見つけました https://velog.io/@moonjang/프로그래머스깊이너비-우선-탐색DFSBFS3-단어-변환-JAVAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol