Word Ladder in Java

As always, we can find best definitions and back ground of anything in wiki. Here is the link for details http://en.wikipedia.org/wiki/Word_ladder.

Here, I just want to give an idea of how can we solve a word ladder puzzle in java. The goal is to find a "path" from a given source word to a destination word, the nodes in the path should only differ by one letter.

From the statement it is clear that its a basic "Graph" problem, and to find the shortest path "Breadth First Search" is the best suited approach.

Here, I have mentioned a basic approach, which works fine, I have written another approach to explain how Graphs work in real world (the basic idea is similar to this). You can find that in my Git repo https://github.com/rajendrag/word-ladder.

Here, we try to replace each character in source string with all possible characters (a to z) and check if the word is exists in the dictionary, if it is there, we add that new word to the 'queue' to process further (like adding vertex in a graph). While we doing this we remove the newly found word from dictionary to avoid recurrences and infinity loop.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class WordLadder2 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        WordLadder2 ladder = new WordLadder2();
        List<String> dictionary = ladder.readWords();
        Word wordLadder = ladder.findLadder("fool", "sage", dictionary);
        ladder.printLadder(wordLadder);
        Word wordLadder1 = ladder.findLadder("cold", "warm", dictionary);
        ladder.printLadder(wordLadder1);
    }

    private void printLadder(Word wordLadder) {
        if(wordLadder == null) {
            System.out.println();
            return;
        }
        printLadder(wordLadder.parent);
        System.out.print(wordLadder.word+" -> ");
        
    }

    private Word findLadder(String source, String dest, List<String> dictionary) {
        if (null == source || null == dest || source.trim().length() == 0 || dest.trim().length() == 0 || null == dictionary || dictionary.size() == 0) {
            return null;
        }
        if (source.length() != dest.length()) {
            return null;
        }

        Queue<Word> queue = new LinkedList<Word>();
        Word start = new Word(source);
        queue.add(start);
        while (!queue.isEmpty()) {
            Word current = queue.poll();
            
            char[] sChars = current.word.toCharArray();
            for (int j=0; j<sChars.length; j++){
                char original=sChars[j];
                  for (char c='a'; c<='z'; c++){
                      if (c==sChars[j]){
                          continue;
                      }
                      sChars[j]=c;
                      String tempStr=String.copyValueOf(sChars);
                      Word newWord = new Word(tempStr);
                      newWord.parent = current;
                      if (tempStr.equals(dest)){
                          return newWord;
                      }
                      
                     if (dictionary.contains(tempStr)){
                         queue.add(newWord);
                         dictionary.remove(tempStr);
                     }
                }
                sChars[j]=original;
          }
        }
        return null;
    }

    private List<String> readWords() {
        List<String> words = new ArrayList<String>();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File("wordfile.txt")));
            String word = null;
            while ((word = br.readLine()) != null) {
                words.add(word.toLowerCase());
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return words;
    }

    class Word {
        String word;
        Word   parent;// the parent, is only is to find the path recursively

        public Word(String word) {
            this.word = word;
        }

    }
}

Here is a sample "wordfile.txt", place this file in projects home directory.

FOOL
CORD
FOUL
FOIL
FAIL
FALL
CARD
PALL
POLE
POOL
POLL
WARM
COOL
PALE
PAGE
POPE
SALE
SAGE
COLD
WARD

Reverse the LinkedList in different ways in Java, iterative, recursive and others

Reversing a linked list is one of the famous interview questions, and many will stumble with this. It is not as simple as it sounds, need to take extra care while establishing the new links.

Lets assume we have a very basic "Node" class, which has one data field (int field) and one reference field to the next.

public class Node {
   int data;
   Node next;
   public Node(int data) {
       this.data = data;
   }
}

Also, we have a very basic LinkedList class which holds the 'head' of our LinkedList.

public class LinkedList{
   Node head;
   public void add() {
       ....
   }

   public void remove() {
       ....
   }
}

Assume, we have initialized our LinkedList with data 10->20->30->40->50, where 10 is the head. Our goal is to reverse this list, and the desired output would be 50->40->30->20->10

Recursive approach:
In general, understanding the recursion will take some time because of little complexity involved with the method stack. I am not going into too many details of the recursion here, but recursion helps us going to the very end of the list and back track from there.

public Node reverseRecursive(Node current) {
     if(current == null || current.next == null) {
          //This is our base case, we have reached the end of the list here, just return null
          return current;
     }
     //recursive call, what is this method returning here? we need to make this method return the 'head' of a so far reversed List.
     Node reversed = reverseRecursive(current.next);
     //back tracking
     //the following two lines are most important and most confusing parts of this approach. We will trace this down with the example
     current.next.next = current;
     current.next = null;
     return reversed;
}

This approach would give us the linear time and memory complexity which is O(n) in both the cases. The memory is O(n) because of the  recursive call stack.

Here, lets go step by step.

•  How do we reveres a list with no items: we just return null (if(current == null) return current;) 
•  How do we reverse a list with one item: we just return the one item (it is already reversed)(if(current.next == null) return current;) 
•  How do we reverse a list with two items: Lets say our initial list 10 -> 20 -> null 

1.  We need to reach to the end (recursive) (Node reversed = reverseRecursive(current.next);) 
2.  Now in the stack, we have current as 10, current.next is 20 
3.  Here we need to set 20.next = 10 correct? so current.next.next = current; 
4.  Also, we need to remove the link between 10 and 20, that's why current.next = null; 
5.  Last, but not least, we need to return the 'reversed', because that is our new head.

A little more explanation about those critical two lines, if somebody is still confused.

This time, lets a take a bigger list 10 -> 20 -> 30 -> 40 -> null.

stack 1 -> reverseRecursive(10) (current 10, current.next 20)

stack 2 -> reverseRecursive(20) (current 20, current.next 30)

stack 3 -> reverseRecursive(30) (current 30, current.next 40)

stack 4 -> reverseRecursive(40) (current 40, current.next null)

returns 40 (reversed is 40)

current.next.next = current; this becomes 30.next.next = 30; that means, 40.next = 30. (reversing the link)

current.next = null; this means 30.next = null 

Here our intermediate list looks like this, 10 -> 20 -> 30 <- 40. (note: both 20's next and 40's next is pointing to 30)

Here, current.next.next = current; this becomes 20.next.next = 20; that means, 30.next = 20

Intermediate list here looks like 10 -> 20 <- 30 <- 40. (note: both 10's next and 30's next is pointing to 20)
In the final call stack, our list becomes 10 <- 20 <- 30 <- 40

current.next = null makes the list look like null <- 10 <- 20 <- 30 <- 40

If we observe, our 'reversed' never changed once we initialized for the first time which was with node 40, which is our new head. Hope this will make little clear.

Iterative approach:
It is straight forward, but need to pay attention to the little details. The idea would be keep track of the previous item in each iteration, point the current's next to the previous and re initialize previous with current.

public Node reverse(Node n) {
 Node current= n;
 Node previous = null;
 while(current != null) {
  Node next = current.next; //keep the reference of the next element as we are going to set the current.next to something else (previous)
  current.next = previous; //back link, current's next should point to previous
  previous = current; // make the current as previous (new intermediate header) for next iterations
  current = next; // continue with the next
 }
 return previous; // this is our new header.
}

With this approach, we get O(n) time complexity as we need visit each element in the list once, and O(1) memory complexity as we are storing one extra "next" variable.

Look and say sequence puzzle in Java (1 11 21 1211 .....)

I recently came across with a question from one of my friends: The question is simple generate "nth" number in "Look and Say Sequence" given "1" as the initial string to start with. Here are more details about this sequence http://en.wikipedia.org/wiki/Look-and-say_sequence.

Look and Say Sequence is something like 1, 11, 21, 1211, 111221, 312211 and so on.. We need to find the nth number with in that sequence.

I thought it would be a very straight forward iterative approach and I could solve it in few minutes. However I faced few hiccups because of less paid attention.

Here is my solutions and I will explain the mistake I made in my first go.

private List<String> lookAndSayOf(int n) {
        List<String> results = new ArrayList<String>();
        results.add("1");
        for(int i=0; i<n; i++) {
            String token = results.get(i);
            char[] chars = token.toCharArray();
            String currentToken = "";
            int count = 0;
            char current = chars[0];
            for(int k=0; k<chars.length; k++) {
                if(current == chars[k]) {
                    count++;
                } else {
                    currentToken = currentToken+""+count+current;
                    count = 1;
                    current = chars[k];
                }
            }
            currentToken = currentToken+""+count+current;
            results.add(currentToken);
        }
        return results;
    }

Here two important things that we may miss in our first (I missed the second one)
- currentToken = currentToken+""+count+current; is required in both places (one is inside the loop and other is at the end of the loop. The inner one is to append the characters when there is a switch. The outer one is for the last switch. The work around to avoid the second statement (after the inner loop), add an extra space (extra character) at the end of the token something like String token = results.get(i)+" ";. This will make the loop run one extra time and we dont need the second statement.
- count = 1; We need to set the count back to 1 instead of zero.