127. 单词接龙

参考127. 单词接龙。

题目

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 *从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

解题思路

• 广度优先搜索：构造 有向图 ,进行广度优先搜索,这里额外给出一种优化方法。

广度优先搜索

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //构造有向图+bfs
        HashMap<String,Integer> map = new HashMap<>();//记录到达节点步数
        map.put(beginWord,1);
        Deque<String> q = new ArrayDeque<>();
        q.add(beginWord);
        while(q.size() > 0) {
            String word = q.poll();
            if(word.equals(endWord)) return map.get(word);
            char[] wordc = word.toCharArray();
            Iterator<String> it = wordList.iterator();
            while(it.hasNext()) {
                String next = it.next();
                char[] nextc = next.toCharArray();
                int cnt = 0;
                for(int i = 0; i < wordc.length; i++) if(wordc[i] != nextc[i]) cnt++;
                if(cnt == 1) { //只差一个可以增加出边
                    it.remove();
                    map.put(next,map.get(word)+1);
                    q.add(next);
                }
            }
        }
        return 0;
    }
}

优化

由于wordList长度很长(5000),而单词长度在10以内,可以反向使用哈希表判断Word的可能出边是否在wordList中来优化判断是否满足出边条件.

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //构造有向图+bfs
        int count = 0;
        //优化出边判断
        HashSet<String> set = new HashSet<>(wordList);
        Deque<String> q = new ArrayDeque<>();
        q.add(beginWord);
        while(q.size() > 0) {
            count ++;
            int size = q.size();
            while(size-- > 0){
                String word = q.poll();
                if(word.equals(endWord)) return count;
                char[] wordc = word.toCharArray();
                for(int i = 0; i < wordc.length; i++) {
                    char wordi = wordc[i];
                    for(char c = 'a'; c <= 'z'; c++) {
                        if(wordi == c) continue;
                        wordc[i] = c; 
                        String newword = new String(wordc);
                        if(set.contains(newword)) {
                            q.add(newword);
                            set.remove(newword);//彷重复访问
                        }
                        wordc[i] = wordi;//回溯恢复
                    }
                }
            }
        }
        return 0;
    }
}

2023.06.09