Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 127] Word Ladder



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

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

For example,

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

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


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


Frequency 5
Difficulty 3
Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)


This is an extremely difficult question.


  1. This question is find shortest path, so we shall choose BFS over DFS.

  2. Since finding an element in HashSet is O(1) time, we can generate all the possible strings of distance = 1 and check if they are in the dictionary. In this way, we reduce time complexity from O(m x n) to O(m x 26).

  3. If a word is found from the dictionary, remove it.

For the 3rd point, we remove the word from dict. It might be hard to understand. This blog explains it clear enough.





对于本题来说,是没有什么影响的,因为到dog距离都是3,到dig距离都是4。但是后面我们做word ladder 2的时候,如果没有考虑这个情况,将是非常致命的,因为题目要求输出最短路径的所有情况

(2)在更下层我们才能够遍历到该元素。比如hot->dot->dog->dig和hot->hat->dat->dag->dog->dig,如果第一次我们找到了dog并且将其删除,那么第二次我们实际上是找不到这个元素的。这样对于本题来说,没有任何影响。对于word ladder 2来说,因为也是要输出最短路径,所以也不会有任何影响。


BFS solution

This is similar to the code posted in this article.

public int ladderLength(String start, String end, HashSet<String> dict) {
    if (start.equals(end)) return 1;
    LinkedList<String> words = new LinkedList<String>();
    LinkedList<Integer> nums = new LinkedList<Integer>();
    while (!words.isEmpty()) {
        String word = words.remove();
        int num = nums.remove();
        // otherwise, change each char in word, and find it from dict
        char[] charArr = word.toCharArray();
        for (int i = 0; i < charArr.length; i++) {
            char originChar = charArr[i];
            for (char j = 'a'; j <= 'z'; j++) {
                charArr[i] = j;
                String newWord = new String(charArr);
                if (newWord.equals(end))
                    return num + 1;
                if (dict.contains(newWord)) {
                    nums.add(num + 1);
            charArr[i] = originChar;
    return 0;