9
\$\begingroup\$

Please treat this as a interview at a top tech firm, and share your thoughts on how you think I did. Be honest, and leave no stone unturned.

Problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time. Each intermediate word must exist in the dictionary

For example,

Given:

  • start = "hit"
  • end = "cog"
  • dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Time Complexity: \$O(n^2)\$ (please confirm)

Space complexity: \$O(n)\$

My code:

   private static int ladderLength(String start, String end, HashSet<String> dict) {
        Deque<String> wordSearch = new ArrayDeque<>();
        Deque<Integer> lengthCount = new ArrayDeque<>();
        wordSearch.add(start);
        lengthCount.add(1);
        while(!wordSearch.isEmpty()){
            String analyzing  = wordSearch.poll();
            int curCount = lengthCount.poll();
            if(analyzing.equals(end)){
                return curCount;
            }
            for(int j = 0; j < analyzing.length(); j++){
                for(char i = 'a'; i <= 'z'; i++){
                    char[] possibleMatch = analyzing.toCharArray();
                    possibleMatch[j] = i;
                    String checkMatch = new String(possibleMatch);
                    if(dict.contains(checkMatch)){
                        dict.remove(checkMatch);
                        lengthCount.add(curCount + 1);
                        wordSearch.add(checkMatch);
                    }
                }
            }
        }
        return 0;
   }
\$\endgroup\$
7
\$\begingroup\$

First of all, I really liked that your logic doesn't need to compare lengths: as soon as a match is found, it must be one of the shortest lengths, nice! And when the end is unreachable, the method returns 0, an impossible answer (since a valid length must be >= 1), so that's good too.

A couple of things can be improved.


Choose the right interfaces

Your method should work with Set<String> dict, and should not limit users to HashSet<String> dict.

Choose the right classes

A Deque is a collection that supports element insertion and removal at both ends. That's more than what you need. A Stack would have been enough for your purpose.

Simplify the inner for loops

The inner for loops are a bit wasteful and can be simplified. You are basically iterating over all possible 1-letter differences and check if in the dictionary. Instead, you could iterate elements of the dictionary and see if they have 1 letter difference. For example like this:

for (String item : dict.toArray(new String[dict.size()])) {
    if (isSingleCharDiff(analyzing, item)) {
        dict.remove(item);
        lengthCount.add(curCount + 1);
        wordSearch.add(item);
    }
}

Discrepancy with the specs

The problem description says:

dict = ["hot","dot","dog","lot","log"]

With this exact input your method returns 0 because it will never reach end. The fix is simple enough, just add it to the dictionary somewhere near the start:

dict.add(end);

A wasted operation

Before the while loop, you do this:

wordSearch.add(start);
lengthCount.add(1);

but then inside the loop you immediately pop them. You could rework the code to eliminate that wasted operation:

String analyzing = start;
int curCount = 1;
while (true) {
    if (analyzing.equals(end)) {
        return curCount;
    }
    for (String item : dict.toArray(new String[dict.size()])) {
        if (isSingleCharDiff(analyzing, item)) {
            dict.remove(item);
            lengthCount.add(curCount + 1);
            wordSearch.add(item);
        }
    }
    if (wordSearch.isEmpty()) {
        break;
    }
    analyzing = wordSearch.pop();
    curCount = lengthCount.pop();
}
\$\endgroup\$
  • \$\begingroup\$ @janos thank you for your time, is my complexity correct? \$\endgroup\$ – bazang Apr 26 '14 at 17:32
  • \$\begingroup\$ @janos also, why should I use an interface as the apparent state? \$\endgroup\$ – bazang Apr 26 '14 at 17:33
  • \$\begingroup\$ You implementation doesn't use any unique features of a HashSet. It would work just the same with any other Set, for example a TreeSet. Using a Set is good enough for your case, and allows the widest possible uses. \$\endgroup\$ – janos Apr 26 '14 at 18:37

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.