BFS_6:字串变换

BFS_6:字串变换

abcd xyz
abc xu
ud y
y yz

3

问题分析:

既然说到最少的变换步数，那无非就想到了BFS，但是这题想要拿满分不容易，第一个就是你压根不知道有多少个变换规则，所以只能拿while做循环输入，这就会出现一个问题，就是while（sc.hasNext）就会进入死循环，必须重写Scanner的方法才能进行输入。第二个就是给出的样例太过于简单，要是按照给出的样例写只能拿到60-80分，因为最后一个样例比较出人意料，最少的变换次数，那肯定开头与目标串相同的部分不能被替换，所以就需要一个flag来记录是否有相同的部分，并且p找出相同部分的长度。
最后一个样例如下：

abaaaba abcdaba
a b
b d
d e
e f
f g
g c

8

二、使用步骤

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
public class BFS_6 {
    static class MyScanner{
        BufferedReader reader;
        StringTokenizer tokenizer;
        //构造方法
        public MyScanner(InputStream is) {
            reader = new BufferedReader(new InputStreamReader(is),32768);
            tokenizer = null;
        }
        public String next(){
            while (tokenizer == null || !tokenizer.hasMoreTokens()){
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        public boolean ready() throws IOException {
            return reader.ready();
        }
    }
    static class Node{
        String s;
        int step;

        public Node(String s, int step) {
            this.s = s;
            this.step = step;
        }
    }
    static int N = 7,n;
    static  String startS,endS;
    static String[][] rule = new String[N][2];
    static String s1,s2 = null;
    static boolean flag = false;
    public static void main(String[] args) throws IOException {
        MyScanner myScanner = new MyScanner(System.in);
        startS = myScanner.next();endS = myScanner.next();
        n  = 0;
        while(myScanner.ready()){
            s1 = myScanner.next();
            s2 = myScanner.next();
            rule[n][0] = s1;
            rule[n][1] = s2;
            n++;
        }
        int p = 0;
        char[] s = startS.toCharArray();
        char[] e = endS.toCharArray();
        while (p<Math.min(s.length,e.length)){
            if(s[p]!=e[p]){
                flag = true;
                break;
            }
            p++;
        }
        if(flag){
            s1 =  startS.substring(0,p);
            startS = startS.substring(p);
        }
        Node node = new Node(startS,0);
        bfs(node);
    }

    public static void bfs(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            Node cur = queue.peek();
            //结束条件
            if(flag){
                if((s1+cur.s).equals(endS)){
                    System.out.print(cur.step);
                    return;
                }
            }else {
                if(cur.s.equals(endS)){
                    System.out.print(cur.step);
                    return;
                }
            }

            if(cur.step>10) {
                System.out.print("NO ANSWER!");
                return;
            }
            //开始枚举规则
            for (int i = 0; i < n; i++) {
                if(cur.s.contains(rule[i][0])){
                    int index = cur.s.indexOf(rule[i][0]);
                    //别漏了这个index 下面的length为索引开头加上被替换的长度，再插入一个任意长度的S
                    int length = index + rule[i][0].length();
                    StringBuilder s=new StringBuilder(cur.s).replace(index, length, rule[i][1]);
                    Node temp = new Node(s.toString(),cur.step+1);
                    queue.offer(temp);
                }
            }
            queue.poll();
        }
    }
}