Leetcode P0126"Word Ladder II" 题解

博文中会简要介绍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:

Only one letter can be changed at a time.

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"]
]

最基本的思路是通过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;
    }
}

聖地亞歌

Leetcode P0126"Word Ladder II" 题解

Search

Table of Contents