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 ->