聖地亞歌

Leetcode P0126"Word Ladder II" 题解

2020/09/11 Leetcode

博文中会简要介绍Leetcode P0126题目分析及解题思路。

“Word Ladder II”是p0127的变形题，这道题是一道相对较难的广度优先搜索题目，利用初始的word数组构造一个无向图，每个结点代表一个单词，然后从起始单词所代表的结点开始BFS，然后记录所有同层的解即可。

GGiven two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
Plaintext

最基本的思路是通过word数组来构建一个无向图，然后从起始单词所指向的结点使用广度优先搜索，这样一来一旦搜索到和结束单词一样的单词，此时的路径长度一定是最短的，而所有和这条路径一样短的其他路径必然与这个路径处在同一层。 并且我们可以通过反向映射，即将单词改变一个字母后可能产生的形态（即Wildcards）映射到可以具有这样形态的实际单词上，来优化BFS对邻接结点的遍历。

以下是Java的题解代码实现。

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        wordList.add(beginWord);
        int N = wordList.size();
        
        Map<String, List<Integer>> wildcard2WordsMap = new HashMap<>();
        Map<Integer, List<String>> word2WildcardsMap = new HashMap<>();
        // Construct the map, by mapping words to their generic wildcards
        for (int itr=0; itr<N; ++itr) {
            String word = wordList.get(itr);
            char[] chars = word.toCharArray();
            
            for (int idx=0; idx<chars.length; ++idx) {
                chars[idx] = '*';
                
                String wildcard = String.valueOf(chars);
                // Update the mapper, mapping words to their generic wildcards
                List<Integer> words = wildcard2WordsMap.getOrDefault(wildcard, new ArrayList<>());
                words.add(itr);
                wildcard2WordsMap.put(wildcard, words);
                
                // Update the mapper, mapping generic wildcards to their word
                List<String> wildcards = word2WildcardsMap.getOrDefault(itr, new ArrayList<>());
                wildcards.add(wildcard);
                word2WildcardsMap.put(itr, wildcards);
                chars[idx] = word.charAt(idx);
            }
        }
        
        // BFS
        List<List<String>> ladders = new ArrayList<>();
        
        Queue<Pair<Integer, List<String>>> queue = new LinkedList<>();
        boolean[] isVisited = new boolean[N];
        int shortest = -1;
        
        List<String> sequence = new ArrayList<>();
        sequence.add(wordList.get(N-1));
        queue.add(new Pair<>(N-1, sequence));
        while (!queue.isEmpty()) {
            Pair<Integer, List<String>> u = queue.poll();
            if (shortest != -1 && u.getValue().size() >= shortest)
                break;
            
            isVisited[u.getKey()] = true;
            // Scan through all the generic wildcards
            for (String wildcard: word2WildcardsMap.get(u.getKey())) {
                
                // Scan through all the words that have such a generic wildcard
                for (int index: wildcard2WordsMap.get(wildcard)) {
                    // Extend the path
                    List<String> ladder = new ArrayList<>(u.getValue());
                    ladder.add(wordList.get(index));
                    
                    // Find a path
                    if (endWord.equals(wordList.get(index))) {
                        ladders.add(ladder);
                        shortest = ladder.size();
                    }
                    
                    if (!isVisited[index])
                        queue.add(new Pair<>(index, ladder));
                }
            }
        }
        
        return ladders;
    }
}
Java

Search