5
\$\begingroup\$

Lil' preparation before the interview. This is my solution to the problem in title. The code is pretty straight forward. Requesting suggestions for improvement and also verification of complexity, which I guess is O(26n)

public class CatToDog {

        static Set<String> dictionary;

        static {
            dictionary = new HashSet<String>();
            dictionary.add("camera");
            dictionary.add("cat");
            dictionary.add("cot");
            dictionary.add("cot");
            dictionary.add("dome");
            dictionary.add("dot");
            dictionary.add("dog");

    //        dictionary = new TreeSet<String>();
    //        BufferedReader br = null;
    //        try {
    //            try {
    //                br = new BufferedReader(new FileReader("/Users/ameya.patil/Desktop/text.txt"));
    //                String line;
    //                while ((line = br.readLine()) != null) {
    //                    dictionary.add(line.split(":")[0]);
    //                }
    //
    //            } finally {
    //                br.close();
    //            }
    //        } catch (Exception e) {
    //            throw new RuntimeException("Error while reading dictionary");
    //        }

        }

        private CatToDog () { };

        public static List<String> listWords(String startWord, String endWord) {
            final Queue<String> queue = new LinkedList<String>();
            final Map<String, String> backTrack = new HashMap<String, String>();
            queue.add(startWord);
            backTrack.put(startWord, null);

            while (!queue.isEmpty()) {
                String currentWord = queue.poll();
                if (currentWord.equals(endWord)) {
                    return mapToList(backTrack, endWord);
                }
                addValidOneChangeWords(currentWord, queue, backTrack);
            }
            return Collections.EMPTY_LIST;
        }

        private static void addValidOneChangeWords(String startWord, Queue<String> queue, Map<String, String> backTrack) {
            for (int i = 0; i < startWord.length(); i++) {
                char[] endWord = startWord.toCharArray();
                for (char ch = 'a'; ch < 'z'; ch++) {
                    endWord[i] = ch;
                    String word = new String(endWord);
                    if (validate(word, backTrack, startWord)) {
                        queue.add(word);
                        backTrack.put(word, startWord);
                    }
                }
            }
        }

        private static boolean validate(String word, Map<String, String> backTrack, String startWord) {
            return dictionary.contains(word) && !backTrack.containsKey(word) && !word.equals(startWord);
        }

        private static List<String> mapToList (Map<String, String> backTrack, String endWord) {
            final List<String> wordList = new ArrayList<String>();
            String word = endWord;
            while (backTrack.containsKey(word)) {
                wordList.add(word);
                word = backTrack.get(word);
            }
            Collections.reverse(wordList);
            return wordList;
        }

        public static void main(String[] args) {
           for (String string :  listWords("cat", "dog")) {
               System.out.println(string);
           }
        }
    }
\$\endgroup\$
7
  • 2
    \$\begingroup\$ I certainly hope the complexity is not O(26^n) .... \$\endgroup\$ – rolfl Dec 1 '13 at 20:20
  • \$\begingroup\$ @rolfl i could not determined the complexity. maybe mostly i am wrong when i came up with that answer \$\endgroup\$ – JavaDeveloper Dec 1 '13 at 21:18
  • \$\begingroup\$ no it's O(n) check levenshtein distance \$\endgroup\$ – ratchet freak Dec 1 '13 at 21:54
  • 1
    \$\begingroup\$ I must be missing something, to get the "distance" from v to w, can't you first iterate both in parallel (until the end of either word was hit) and increase the distance by 1 for every character which is not the same at the current position in both strings? At the end, just add the difference in length to the distance. I.e. the difference between camera and cat would be 4, the difference between cat and dog would be 3, between dot and dog just 1. That would be O(n). \$\endgroup\$ – Frerich Raabe Dec 2 '13 at 11:41
  • \$\begingroup\$ Should be each word in the sequence differ from the previous word by only one letter? \$\endgroup\$ – cat_baxter Dec 2 '13 at 11:53
3
\$\begingroup\$

I'm not sure about the exact complexity, but it is certainly huge! One-letter edits are fine to spell check one word given a large dictionary, but does not work if you only have a few words and the edit distance can be arbitrarily large. To look for close words in the dictionary, you should use the Levenshtein distance, as mentioned by ratchet freak. (Implementing the Levenshtein distance is a good idea.)

//        dictionary = new TreeSet<String>();
//        ....

Please don't post unused code here unless you want it reviewed too.

private CatToDog () { };

A default constructor is provided by Java already, only use that if you need to put something in there.

public static List<String> listWords(String startWord, String endWord) {
    final Queue<String> queue = new LinkedList<String>();
    final Map<String, String> backTrack = new HashMap<String, String>();
    queue.add(startWord);
    backTrack.put(startWord, null);

    while (!queue.isEmpty()) {
        String currentWord = queue.poll();
        if (currentWord.equals(endWord)) {
            return mapToList(backTrack, endWord);
        }
        addValidOneChangeWords(currentWord, queue, backTrack);
    }
    return Collections.EMPTY_LIST;
}

How do you know this is the shortest path? It feels a lot like depth first search, but I think you want to implement Dijkstra's algorithm instead to be able to notice shorter subpaths.

private static void addValidOneChangeWords(String startWord, Queue<String> queue, Map<String, String> backTrack) {
    for (int i = 0; i < startWord.length(); i++) {
        char[] endWord = startWord.toCharArray();
        for (char ch = 'a'; ch < 'z'; ch++) {
            endWord[i] = ch;
            String word = new String(endWord);
            if (validate(word, backTrack, startWord)) {
                queue.add(word);
                backTrack.put(word, startWord);
            }
        }
    }
}

You're only focusing on one-letter edits here, but what about deletions, insertions and even transpositions (dog -> dgo)? The Damerau-Levenshtein distance handles them.

And finally, mapToList is poorly named: I already know that the type change, I want to know about semantics! Something like editPath would be better.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ I don't see a good way to write this recursively. You need a PriorityQueue which in this trivial case degenerates to a Queue, not a Stack. One also needs to keep an already-visited set, which is a bit uglier in recursive code as well. So I prefer the OP's choice of looping over a Queue over a recursive algorithm here. \$\endgroup\$ – CodesInChaos Dec 2 '13 at 11:18
  • \$\begingroup\$ Thanks for your comment. Unless I'm mistaken again, if it's a BFS (ie. needs a Queue, not a Stack), it's also easy with a recursive function (just decide where you call recursively). The already-visited set can easily be handled as a parameter, but it has to be clear that it's going to be modified "outside" of the function. \$\endgroup\$ – Quentin Pradet Dec 3 '13 at 9:06
  • \$\begingroup\$ I can't think of a simple way to write a BFS recursively. \$\endgroup\$ – CodesInChaos Dec 3 '13 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.