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
HashSet dictionary = 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