Word Ladder

A word ladder puzzle begins with two words and to solve the puzzle one must find a chain of other words to link the two, in which two adjacent words differ by one letter.

Write a program to implement Word Ladder using set?

Algorithm Explanation

	Pass arguments to the utility function.
	The words assigned to start word and an end word. The program must change the start word into the end word progressively.
	Each step consists of a single letter substitution.
	Return the Word Ladder to the main function and display the result.

Source Code

package com.dsacode.DataStructre.set;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
class Word { 
    String word; 
    Word   parent;
 
    public Word(String word) { 
        this.word = word; 
    } 
 
} 
 
public class WordLadder {
     
   
    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; 
    } 
   
   
   
    public static void main(String[] args) { 
        WordLadder ladder = new WordLadder(); 
  
        List < String > dictionary = new ArrayList < String >();
        dictionary.add("fool");
        dictionary.add("cord");
        dictionary.add("foul");
        dictionary.add("foil");
        dictionary.add("fail");
        dictionary.add("fall");
        dictionary.add("card");
        dictionary.add("pall");
        dictionary.add("pole");
        dictionary.add("pool");
        dictionary.add("poll");
        dictionary.add("warm");
        dictionary.add("cool");
        dictionary.add("pale");
        dictionary.add("page");
        dictionary.add("pope");
        dictionary.add("sale");
        dictionary.add("sage");
        dictionary.add("cold");
        dictionary.add("ward");
        System.out.println("Find the ladder 'fool' and 'sage'");
        Word wordLadder = ladder.findLadder("fool", "sage", dictionary); 
        ladder.printLadder(wordLadder);
        System.out.println("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println("\nFind the ladder 'cold' and 'warm'");
        Word wordLadder1 = ladder.findLadder("cold", "warm", dictionary); 
        ladder.printLadder(wordLadder1); 
    } 
     
 
}

Output

Find the ladder 'fool' and 'sage'
fool -> pool -> poll -> pall -> pale -> sale -> sage ->
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Find the ladder 'cold' and 'warm'
cold -> cord -> card -> ward -> warm ->