7
\$\begingroup\$

I wrote a program that calculates the minimum number of rungs of a "word ladder" between a starting word and an ending word. The function minlinks() takes in 3 arguments: a list which acts as a dictionary, a starting word, and an ending word. It returns an int[] of two values; the first is minimum number of links in the word ladder, the second is the number of paths with said number of links.

Example of a word ladder:

words = [rain, ruin, gain, grin, grit, main, pain, pair, pail, mail] from = sail to = ruip

Returns: [6, 2]

There are two links of length six and no shorter links.

sail mail main rain ruin ruip
sail pail pain rain ruin ruip

As written, the program works. However, as someone new to coding in Java, I would appreciate others commenting on the coding style. Also, I included a test case in the main method which runs in about 4 seconds on my computer, which is too slow. Is there any way to optimize this program to make it run faster?

import java.util.*;
public class WordLinksMin {

    // Helper method, returns true if two words are one letter away from each other.
    public boolean isStep(String from, String s) {
        if (from.length() != s.length()) {
            return false;
        }
        int differences = 0;
        for (int charIndex = 0; charIndex < from.length(); charIndex++) {
            if (from.charAt(charIndex) != s.charAt(charIndex)) {
                differences++;
            }
            if(differences > 1) break;
        }
        return (differences == 1);
    }

    // given an array of words (our "dictionary"), the starting word and the ending word. find the minimum number of links between start and end using the given dictionary.
    // function returns int[] array {min number of links, number of paths with min number of links}
    public int[] minLinks(String[] words, String start, String end) {
        int firstFindSize = 0;
        int[] result = new int[2];
        // Convert String[] into a HashSet.
        List < String > myWordList = new ArrayList < String > (Arrays.asList(words));
        Set < ArrayDeque < String >> allStacks = new HashSet < ArrayDeque < String >> ();
        if (myWordList.size() == 0) return result;
        // We will implement BFS with a stack of queues
        ArrayDeque < ArrayDeque < String >> wordQueue = new ArrayDeque < ArrayDeque < String >> (); //one queue of stacks to track nodes visited
        // initialize the parent node, which is a stack containing starting word.
        ArrayDeque < String > startStack = new ArrayDeque < String > ();
        startStack.push(start);
        wordQueue.add(startStack);
        // we act differently in while loop based on whether we have already found a path from start to end
        boolean firstFind = true;

        while (!wordQueue.isEmpty()) {

            ArrayDeque < String > currentStack = wordQueue.pop();

            String currentWord = currentStack.peek();
            if (isStep(currentWord, end) && currentStack.size() >= 2 && firstFind) { //no direct link
                currentStack.push(end);
                allStacks.add(currentStack);
                firstFind = false; //after finding first stack, we know the stack size we must look for, for any other path of the same length.
                firstFindSize = currentStack.size();
                //System.out.println((firstFindSize));
                //System.out.println("before ff");
                //System.out.println(currentStack);

            } else if (isStep(currentWord, end) && currentStack.size() == firstFindSize - 1 && !firstFind) {
                currentStack.push(end);
                //System.out.println("not ff");
                //System.out.println(currentStack);
                allStacks.add(currentStack);
            }

            if (firstFind) {
                for (String word: myWordList) {
                    if (isStep(currentWord, word) && !currentStack.contains(word)) {
                        ArrayDeque < String > wordStack = new ArrayDeque < String > (currentStack);
                        wordStack.push(word);
                        wordQueue.add(wordStack);
                    }
                }
            }
        }

        result[1] = allStacks.size();
        result[0] = firstFindSize;
        System.out.printf("%d %d", result[0], result[1]);
        return result;
    }

    public static void main(String[] args) {
        WordLinksMin a = new WordLinksMin();
        String[] b = {
                "abcde", "abcda", "abcdb", "abcdc", "abcdd", "abcdf", "abcdg", "abcdh", "abcdi", "abcdj", "abcdk", "obcda", "obcdb", "obcdc", "obcdd", "obcdf", "obcdg", "obcdh", "obcdi", "obcdj", "obcdk", "obcdm", "obadm", "obbdm", "obddm", "obedm", "obfdm", "obgdm", "obhdm", "obidm", "objdm", "obkdm", "okadm", "okbdm", "okddm", "okedm", "okfdm", "okgdm", "okhdm", "okidm", "okjdm", "okkdm", "okodm", "okokm" 
        };
        long startTime = System.nanoTime();
        System.out.println(a.minLinks(b, "abode","okoko"));
        long endTime = System.nanoTime();
        long duration = (endTime - startTime);
        System.out.println(duration);
        //      for (List<String> list : a.listOfPaths){
        //          for (String s : list) {
        //              System.out.print(s+" ");
        //          }
        //          System.out.println();
        //      }
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  1. About the algorithm itself. I do not fully understand the algorithm you are using now, but it looks pretty strange(a bfs with a stack of queues?) and, as you have said, it is inefficient. So let's redesign it:

    • Let's start with a clear problem statement in terms of graphs: given a graph where each node corresponds to a word and there is a bidirectional edge between two nodes iff the words differ in exactly one letter, find the shortest path between two nodes and the number of shortest paths.

    • Before running the breadth-first search, let's build the graph explicitly and forget about the words. We can do by simply checking each pairs of words as you do it now.

    • Now let's run a BFS on this graph and get the length of the shortest path.

    • How to find the number of such paths? We have the following formula: f(v) = sum f(u) for all u such that dist[u] = dist[v] - 1 and f(start) = 1. We can compute it efficiently using memoization.

    • The time complexity is O(len * N ^ 2), where len is the length of the words and N is their number. It should be very fast for such a small dictionary if implemented properly.

  2. The minLinks method seems too big to me. Taking into account a new algorithm described in 1., I'd do it this way:

    • Create three separate methods: one for building the graph, another one for running the breadth-first search and the last one for counting the number of shortest path.

    • We can go even further and create a separate graph class so that this class has to only build an appropriate graph. It is definitely good for code reuse and makes a good sense from the design point of view: a graph and breadth-first search is a very general notion and it has almost nothing to do with words.

Summary: both 1. and 2. express the same idea(from different point of views): we can represent this problem as a graph problem using standard graph concepts and algorithms and separate it from words to achieve better performance and better design.

\$\endgroup\$
1
  • \$\begingroup\$ thank you! The answer is pretty comprehensive and tells me what I need to know. \$\endgroup\$ Mar 17, 2015 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.