Word Ladder Solution in Java using ArrayList

Question

Word Ladder

Given a start word and a goal word, convert the start word to the goal word by changing one letter at a time. Each step must also be a valid word.

Is my code modular? I mean are functions are concise, class design etc.? Could someone please review the code and let me know if code is good and if it has some design issues. Any tips on improving the design, and making the code cleaner, change variable names?

Used dictionary at this URL.

package test1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class WordLadder {

    private final HashSet<String> dic= new HashSet<>();
    private final List<Node> nodeQ= new LinkedList<>();
    private final HashSet<Node> visitedNodes= new HashSet<>();
    private final String in;
    private final String target;

    public WordLadder(String i, String t){
        in=i;
        target= t;
    }

    public static void main(String[] args) throws IOException {
        WordLadder wl= new WordLadder("stone","money");
        //WordLadder wl= new WordLadder("stone","chore");
        //WordLadder wl= new WordLadder("stone","choky");
        //WordLadder wl= new WordLadder("charge","comedo");     //takes time ~ 3 mins- seems hardest

        wl.loadDictionary();
        if(!wl.dic.contains(wl.in)||!wl.dic.contains(wl.target)){
            System.out.println("error words not in dic");
        }

        wl.nodeQ.add(new Node(wl.in));

        wl.getPaths();
    }

    private void getPaths(){
        long st= System.currentTimeMillis();
        while(!isMatchFound()){
            Node n= selectNext();
            nodeQ.remove(n);

            addNextWordsToQ(n);

            visitedNodes.add(n);
        }

        System.out.println("nodeQ- \n"+nodeQ);
        System.out.println("visitedNodes- \n"+visitedNodes);

        long end= System.currentTimeMillis();
        System.out.println("time taken in sec~ "+ (end-st)/1000);
        System.out.println("time taken in min~ "+ (end-st)/60000);
    }

    private Node selectNext(){
        Node sel= null;
        int minMatch=-1;
        int match;

        for(Node n: nodeQ){
            match=0;
            for(int i=0; i<target.length(); i++){
                if(n.str.charAt(i)== target.charAt(i)) {
                    match++;
                }
            }
            if(match>minMatch){
                sel=n;
                minMatch=match;
            }
        }
//      System.out.println(sel.str+" "+minMatch);
        return sel;
    }

    //Add next possible combinations to the nodeQ
    private void addNextWordsToQ(Node n){
        String s= n.str;
        for(int i=0;i<s.length();i++){
            String regex= s.substring(0,i)+"."+s.substring(i+1);
            Pattern p= Pattern.compile(regex);
            for(String d: dic){
                Matcher m= p.matcher(d);
                if(!d.equals(s) && s.length()==d.length() 
                        && m.find() && !isNodeVisited(d)){
                    nodeQ.add(new Node(d,n));
                }
            }
        }
    }

    //Check nodeQ to see if word ladder is solved
    private boolean isMatchFound(){
        for(Node n: nodeQ){
            if(target.equals(n.str)){
                System.out.println(n);
                return true;
            }
        }
        return false;
    }

    private boolean isNodeVisited(String add){
        for(Node n: visitedNodes){
            if(n.str.equals(add)){
                return true;
            }
        }
        return false;
    }

    private void loadDictionary() throws IOException{
        InputStream is= WordLadder.class.getClassLoader().getResourceAsStream("dictionary.txt");
        BufferedReader br= new BufferedReader(new InputStreamReader(is));
        String s= br.readLine();
        while(s!=null){
            dic.add(s);
            s= br.readLine();
        }
    }
}

class Node{
     String str;
     final List<String> path= new ArrayList<>();

    public Node(String str){
        this.str=str;
    }

    public Node(String str, Node parent){
        this.str=str;
        path.addAll(parent.path);
        path.add(parent.str);
    }

    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((str == null) ? 0 : str.hashCode());
        return result;
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (str == null) {
            if (other.str != null)
                return false;
        } else if (!str.equals(other.str))
            return false;
        return true;
    }

    public String toString() {
        return "\n" + str + ", " + path+ "";
    }
}

Answer 1

• Performance

  The most heavy working part of the code seems to be addNextWordsToQ; lets focus on it.

  • One immediate observation is that it does a lot of unnecessary work by trying to match a priori non-matching words of the wrong length. Sort the dictionary by word length in advance (a small one-time investment), and match only against the relevant section.

  • A regex is an overkill. Too many strings are built; the dictionary is traversed too many times (once for each position in the word). The only thing you are really interested in is a Hamming distance between the current word and the candidate word being equal to 1. Hamming distance calculation is as trivial as

    static private int hammingDistance(String s1, String s2) {
        assert(s1.length() == s2.length();
        int distance = 0;
        for (int i = 0; i < s1.length(); ++i) {
            distance += (s1.charAt(i) != s2.charAt(i));
        }
        return distance;
    }
    

  • Order of testing conditions is important. If the node is visited, you may omit matching attempt completely.

  That said, I would change the whole thing to

  private void addNextWordsToQ(Node n) {
      for (String candidate: subdict) {
          if ((!isNodeVisited(d) && (hammingDistance(n.str, d) == 1)) {
              nodeQ.add(new Node(d, n));
          }
      }
  }
  

  • Notice that selectNext in fact calculates Hamming distance, and the code may now be reused.

  • Speaking of selectNext, it also incurs performance penalty. It scans the whole queue each time. You'd be much better off using some sorted collection instead of a linked list. A priority queue comes to mind.

Answer 2

Style

• Using braces {} for single if statements would make your code less errorprone. If you decide to not use them, you should be at least consistent with your style. You are mixing both.

• give your variables some space to breathe.

  while(s!=null){  
  

  will be much more readable like

  while (s != null) {
  

Naming

• reading getPaths() I would expect to get something back by calling this method.
• you shouldn't shorten variable names. You are using a lot of single letter names which is ok for a loop iteration counter, but not like you use them. Improving readability will make Mr.Maintainer happy.

Node

• You should make str final to show that it isn't changed anywhere.

• In the hashCode() method you can remove the result variable and just return the result

  public int hashCode() {
      final int prime = 31;
      return prime + ((str == null) ? 0 : str.hashCode());
  }