[プログラマ](深度優先)単語を変換

2556 ワード
algorithm テキストリンク
ワード変換
条件
1.一度に1文字しか置換できない
2.ワードの単語にしか変換できない
3.各単語はアルファベット小文字のみで構成されています.
4.各単語の長さは3または10以下であり、すべての単語の長さは同じである.
5.単語は3個または50個以上の単語があり、重複する単語はない.
6.beginとtargetは違います.
7.変換できない場合は0を返します.
解答方法
1.与えられた単語を起点として、変換文字ごとにターゲットを探す.
2.単語の単語をdfsで1つずつ比較する.
3.最初の単語とwordslistの1つの単語に異なる文字がある場合はcount+1を用いて再開した単語として最初からwordslistと比較する.
5.このように比較した場合、targetのような単語が出た場合、count値を解答値に格納します.
6.dfsを比較し、count値が以前に保存した答え値(最小値でもよい)より小さい場合、答えの値をより小さいcountに置き換えて保存します.
7.変換できない場合は0と表示されるので、最初は答え値をInteger Max値として保存し、答え値が変わらない場合は0として出力します.
package test;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class test11 {

    public static int answer = Integer.MAX_VALUE;

    public static boolean check(String begin, String target) {

        int c = 0;
        for (int i = 0; i < begin.length(); i++) {
            if (begin.charAt(i) != target.charAt(i)) {
                c++;
            }
        }
        Integer.MAX_VALUE

        return c == 1 ? true : false;

    }

    public static void dfs(String[] sa, String begin, String target, int count, boolean used[]) {
        if (begin.equals(target)) {
            answer = (answer > count) ? count : answer;
            return;
        }

        for (int i = 0; i < sa.length; i++) {
            if (!used[i]) {
                if (check(begin, sa[i]) == true) {
                    used[i] = true;
                    dfs(sa, sa[i], target, count + 1, used);
                    used[i] = false;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("src/test11.txt"))));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        String begin = st.nextToken();
        String target = st.nextToken();

        st = new StringTokenizer(br.readLine());
        int count = Integer.parseInt(st.nextToken());

        String[] sa = new String[count];
        for (int i = 0; i < count; i++) {
            String word = br.readLine();
            sa[i] = word;
        }

        boolean used[] = new boolean[count];

        dfs(sa, begin, target, 0, used);

        System.out.println(answer);

    }
}
bfsを使用したルックアップソースコード
JavaScriptでのプロパティによるグループオブジェクト