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\$
1

1 Answer 1

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\$
3
  • \$\begingroup\$ @janos thank you for your time, is my complexity correct? \$\endgroup\$
    – bazang
    Apr 26, 2014 at 17:32
  • \$\begingroup\$ @janos also, why should I use an interface as the apparent state? \$\endgroup\$
    – bazang
    Apr 26, 2014 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, 2014 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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