(UVA) Word Transformation - Solution 1

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370

The solution below used Breadth-First Search (BFS) to solve this problem.

For every word that we visit in the BFS method, we check all the other words. If the other word differs only in one character of the current word, we add it in our queue.


import java.io.*;
import java.util.*;

class Main {
    public ArrayList<String> words;
   
    public int bfs(String start, String end) {
        Queue<Counter> queue = new ArrayDeque<>();
        queue.add(new Counter(start, 0));
       
        HashSet<String> visited = new HashSet<>();
       
        while (queue.size() > 0) {
            Counter curr = queue.poll();
            String currS = curr.s;
            int currCount = curr.count;
           
            if (visited.contains(currS)) {
                continue;
            }
            visited.add(currS);
           
            if (currS.equals(end)) {
                return currCount;
            }
           
            for (int i = 0; i < words.size(); i++) {
                if (words.get(i).length() != currS.length()) {
                    continue;
                }
                int count = 0;
                boolean possible = true;
                for (int j = 0; j < currS.length(); j++) {
                    if (currS.charAt(j) != words.get(i).charAt(j)) {
                        count++;
                    }
                    if (count > 1) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    queue.add(new Counter(words.get(i), currCount+1));
                }
            }
        }
       
        return -1;
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = Integer.parseInt(br.readLine());
        br.readLine();
        for (int test = 0; test < numTests; test++) {
            if (test > 0) {
                bw.write("\n"); // blank line between outputs
            }
           
            words = new ArrayList<>();
           
            String word = br.readLine();
            while (!word.equals("*")) {
                words.add(word);
                word = br.readLine();
            }
           
            String line = br.readLine();
            while (line != null && !line.equals("")) {
                String[] s = line.split(" ");
                String start = s[0];
                String end = s[1];
                bw.write(start+" "+end+" "+bfs(start, end)+"\n");
                line = br.readLine();
            }
        }
                                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Counter {
    String s;
    int count;
   
    public Counter(String s, int c) {
        this.s = s;
        count = c;
    }
}