127. Word Ladder

Published on April 13, 2023

Problem 1

This problem is given a start word and an end word, and transforms one letter at a time from the start word to see if the end word can be reached, returning the shortest path of the transformation. The restriction is that each transformed word must be in the given list of words. Look at an example:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Algorithm 1

I used backtracking at first, but didn't write it (forgot about it), and according to the discussion in the discussion forum, the solution written by backtracking will also time out.

How to build a graph to traverse is a key point. In the previous backtracking I have actually implemented this method, because the topic is only limited to lowercase letters, so we can replace the letters in each position in turn to see if they exist in the word list.

Code 1

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        Set<String> seen = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        seen.add(beginWord);
        queue.add(beginWord);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                String str = queue.poll();
                if (str.equals(endWord)) return level;
                for (int i = 0; i < str.length(); i++) {
                    char[] chars = str.toCharArray();
                    for (Character j = 'a'; j <= 'z'; j++) {
                        chars[i] = j;
                        String tempStr = new String(chars);
                        if (!seen.contains(tempStr) && words.contains(tempStr)) {
                            queue.add(tempStr);
                            seen.add(tempStr);
                        }
                    }
                }
            }
            level++;
        }
        
        return 0;
        
    }
}

When the backtracking did not come up with a direct look at the standard answer, the method given is to introduce a pattern as the key value to save the corresponding words that match the pattern. After doing this preprocessing, then just go for the corresponding BFS. The idea is the same.

Code 1-2

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();
        Map<String, List<String>> map = new HashMap<>();
        
        wordList.forEach(word -> {
           for (int i = 0; i < word.length(); i++) {
               String newWord = word.substring(0, i) + "*" + word.substring(i+1, L);
               List<String> list = map.getOrDefault(newWord, new ArrayList<>());
               list.add(word);
               map.put(newWord, list);
           } 
        });
        
        Set<String> visited = new HashSet<>();
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(beginWord, 1));
        visited.add(beginWord);
        
        while (!queue.isEmpty()) {
            Pair<String, Integer> pair = queue.poll();
            String word = pair.getKey();
            Integer level = pair.getValue();
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i+1, L);
                for (String neighbor : map.getOrDefault(newWord, new ArrayList<>())) {
                    if (neighbor.equals(endWord)) {
                        return level + 1;
                    }
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(new Pair(neighbor, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

The time complexity is O(m*m*n). Preprocessing time: traversing all words is m*n, and doing character substitution for each word is m time again, so it is m*n*m. BFS time: same as preprocessing, traversing all words is m*n, and doing character substitution for each word is m time again.

Space complexity: preprocessing space takes m*n*m, bfs queue takes m*n, visited takes m*n.

If method one is used, one m in the above m*n*m needs to be changed to 26, so the advantage and disadvantage of the slight time of these two algorithms lies in the length of each word.

问题1

这个问题是给一个开始单词和一个结束单词，从开始单词开始每次只变换一个字母，看是否可以到达结束单词，返回变换的最短路径。限制是，每次变换的单词都必须在给定的一个单词列表中。看一个例子：

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

算法1

这个题目看到最短路径可以考虑用BFS。我一开始用了回溯，但是没写出来（对回溯有些忘记了），根据讨论区的讨论回溯写出来的解也是会超时的。

所以考虑用普通的BFS。如何构建图来遍历是一个关键点。在之前的回溯其实我已经实现了这种方法，因为题目只限定了是小写字母，那么我们可以对每一个位置的字母进行依次替换看是否存在于单词列表中。

代码1

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        Set<String> seen = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        seen.add(beginWord);
        queue.add(beginWord);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                String str = queue.poll();
                if (str.equals(endWord)) return level;
                for (int i = 0; i < str.length(); i++) {
                    char[] chars = str.toCharArray();
                    for (Character j = 'a'; j <= 'z'; j++) {
                        chars[i] = j;
                        String tempStr = new String(chars);
                        if (!seen.contains(tempStr) && words.contains(tempStr)) {
                            queue.add(tempStr);
                            seen.add(tempStr);
                        }
                    }
                }
            }
            level++;
        }
        
        return 0;
        
    }
}

当回溯没有想出来之后直接看了标准答案，给出的方法是引入了一个pattern来作为键值，保存对应的符合模式的单词。做完这个预处理之后，再去作相应的BFS即可。思路是一样的。

代码1-2

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();
        Map<String, List<String>> map = new HashMap<>();
        
        wordList.forEach(word -> {
           for (int i = 0; i < word.length(); i++) {
               String newWord = word.substring(0, i) + "*" + word.substring(i+1, L);
               List<String> list = map.getOrDefault(newWord, new ArrayList<>());
               list.add(word);
               map.put(newWord, list);
           } 
        });
        
        Set<String> visited = new HashSet<>();
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(beginWord, 1));
        visited.add(beginWord);
        
        while (!queue.isEmpty()) {
            Pair<String, Integer> pair = queue.poll();
            String word = pair.getKey();
            Integer level = pair.getValue();
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i+1, L);
                for (String neighbor : map.getOrDefault(newWord, new ArrayList<>())) {
                    if (neighbor.equals(endWord)) {
                        return level + 1;
                    }
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(new Pair(neighbor, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

时间复杂度是O(m*m*n)。预处理时间：遍历所有的单词是m*n，对每一个单词做字符替换又是m时间，所以是m*n*m。BFS时间：与预处理一样，遍历所有的单词是m*n，对每一个单词做字符替换又是m时间。

空间复杂度：预处理空间需要m*n*m， bfs的queue需要m*n, visited需要m*n。

如果采用方法一，上述m*n*m中的一个m需要改为26，所以这两个算法轻微时间的优劣在于每个单词的长度。