単語変換
3383 ワード
タイトルの説明:1つの単語のリストがあって、1つの初期の単語と1つの最終の単語、初期の単語は単語のリストを通じて次第に最終の単語に変換する必要があって、変換の必要な最短の変換の経路の長さを求めます.変換ルール:abcからcbaに変更すると2文字しか変更できません.変換するたびに単語リストから選択できます.たとえば、初期単語hot、最終単語dog、単語リスト[got,dot,god,dog,lot,log]、最短変換パスは[hot,dot,dog]です.、最短変換パス長は3です.注意:単語リストには最終単語が含まれ、初期単語は含まれません.リストの各単語の長さは、初期単語、最終単語と同じです.リスト内の単語は重複しません.すべてのアルファベットは小文字です.
入力入力データは3行あり、第1の動作は初期単語である.第2の行為の最終単語;第3の動作の単語リストは、単語と単語の間をスペースで分割します.
最短変換パス長を出力します.
サンプル入力hot dog got dot god dog lot log
サンプル出力3
最短パス関連アルゴリズムの検索を求めます.
以下は私の答えです(よく書けないところは指摘してくださいね)、もしあなたが最高の解決策があれば、以下のコメントで、みんなで交流して勉強してください!
入力入力データは3行あり、第1の動作は初期単語である.第2の行為の最終単語;第3の動作の単語リストは、単語と単語の間をスペースで分割します.
最短変換パス長を出力します.
サンプル入力hot dog got dot god dog lot log
サンプル出力3
最短パス関連アルゴリズムの検索を求めます.
以下は私の答えです(よく書けないところは指摘してくださいね)、もしあなたが最高の解決策があれば、以下のコメントで、みんなで交流して勉強してください!
import java.util.ArrayList;
import java.util.Scanner;
public class TestAgain {
static int[][] matrix;//
static int len;//
static ArrayList path;//
static ArrayList> paths;//
public static void main(String[] args) {
//
Scanner scanner = new Scanner(System.in);
String init = scanner.nextLine();
String end = scanner.nextLine();
String list = scanner.nextLine();
scanner.close();
//
len = list.split(" ").length + 1;
String[] vocabulary = new String[len];
vocabulary[0] = init;
int start = 0; //
for (int i = 1; i < len; i++) {
vocabulary[i] = list.split(" ")[i - 1];
if (vocabulary[i].equals(end)) {
start = i;
}
}
//
matrix = nearMatrix(vocabulary);
path = new ArrayList();
paths = new ArrayList>();
//
look(start);
//
int min = Integer.MAX_VALUE;
for (int i = 0; i < paths.size(); i++) {
int k = paths.get(i).size();
if (k < min && paths.get(i).get(k - 1) == 0) {
min = k;
}
}
System.out.println(min + 1);
}
public static void look(int start) {
for (int i = 0; i < len; i++) {
if (matrix[start][i] == 1 && !path.contains(i)) {
path.add(i);
if (i != 0) {
look(i);
} else {
break;
}
}
}
//
paths.add(path);
path = new ArrayList();
int length = paths.get(paths.size() - 1).size();
for (int i = 0; i < length - 1; i++) {
path.add(paths.get(paths.size() - 1).get(i));
}
}
//
public static int[][] nearMatrix(String[] vac) {
int[][] matrix = new int[vac.length][vac.length];
for (int i = 0; i < vac.length; i++) {
for (int j = 0; j < vac.length; j++) {
matrix[i][j] = compare(vac[i], vac[j]);
}
}
return matrix;
}
//
public static int compare(String s1, String s2) {
int k = 0;
for (int i = 0; i < s1.length(); i++) {
if ((s1.charAt(i) + "").compareTo((s2.charAt(i) + "")) != 0) {
k++;
if (k > 1) {
return Integer.MAX_VALUE;
}
}
}
return k;
}
}