google-code-prettify

Friday, 25 January 2013

Travel from string to string (Google Interview question)

Google Interview Question (http://www.careercup.com/question?id=14947965):
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);
    }
}

No comments:

Post a Comment