Given a source string and a destination string write a program to display sequence of strings to travel from source to destination. Rules for traversing:
1. You can only change one character at a time
2. Any resulting word has to be a valid word from dictionary
Example: Given source word CAT and destination word DOG , one of the valid sequence would be
CAT -> COT -> DOT -> DOG
Another valid sequence can be
CAT -> COT - > COG -> DOG
One character can change at one time and every resulting word has be a valid word from dictionary
The solution here includes not only functions but global variables as well.
public class SourceToDestinationString { // Container for the valid words HashSetdictionary = null; // Container for words already passed by a word sequence HashSet visited; public SourceToDestinationString() { super(); visited = new HashSet (); dictionary = new HashSet (); initDictionary(); } private void initDictionary() { // Add the wrods in the dictionary } // Returns all valid words suitable for the next step of the path private ArrayList generateWords(String source, int position) { if (position < 0 || position >= source.length()) return null; ArrayList result = new ArrayList (); for (char ch = 'A'; ch <= 'Z'; ch++) { StringBuffer tmpWord = new StringBuffer(source); tmpWord.setCharAt(position, ch); String word = tmpWord.toString(); if (dictionary.contains(word)) { result.add(word); } } return result; } // The sequence of words is written in the stack 'path' public void sourceToDestinationString(Stack path, String destination) { String source = path.peek(); if (source.equals(destination)) { System.out.print("Solution is "); System.out.println(path); return; } visited.add(source); for (int i = 0; i < source.length(); i++) { ArrayList words = generateWords(source, i); for (String nextWord : words) { if (visited.contains(nextWord)) continue; path.push(nextWord); sourceToDestinationString(path, destination); path.pop(); } } visited.remove(source); } }
Learn Java programming like a pro with the help of our simplified tutorials, examples and frequently asked Java interview questions and answers. Java tutorial for beginners and professional java developers!
ReplyDeleteMORE INFO - Java Interview Questions and Answers