Leetcode: 127. 单词接龙

题目描述

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

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

输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    返回它的长度 5。

示例 2:

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

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

思路

思路1 BFS

可将单词接龙看作更改一个单词的无向图，但是需要记录访问的词，所有词都可分解为将一个字符改成*的通用匹配模式，然后使用该通用模型进行匹配，然后使用BFS对图进行广度优先遍历，在广度优先遍历时需要注意要保存层次信息帮助记录路径长

思路2 双向

同时从开始词和末尾词进行BFS,减少无用边，更快找到路径，结果为路径加和即可

代码

代码1

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        if (beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0 || wordList == null || wordList.size() == 0){
            return 0;
        }
        Map> wordDict = new HashMap<>();
        Map hasVisit = new HashMap();
        Queue> queue = new LinkedList<>();
        hasVisit.put(beginWord, true);
        queue.offer(new HashMap<>(){{put(beginWord, 1);}});
        for(String word: wordList){
            int l = word.length();
            if (!word.equals(beginWord)){
                hasVisit.put(word, false);
            }

            for(int i = 0; i < l; i++){
                String tempStr = word.substring(0, i) + "*" + word.substring(i + 1, l);
                if (!wordDict.containsKey(tempStr)){
                    wordDict.put(tempStr, new ArrayList());
                }
                List tempList = wordDict.get(tempStr);
                tempList.add(word);
                wordDict.put(tempStr, tempList);
            }
        }
        while(!queue.isEmpty()){
            Map node = queue.remove();
            String word = node.keySet().toArray()[0].toString();
            int getLevel = node.get(word);
            if (word.equals(endWord)){
                return getLevel;
            }
            int l = word.length();
            for(int i = 0; i < l; i++){
                String tempStr = word.substring(0, i) + "*" + word.substring(i + 1, l);
                if (wordDict.get(tempStr) == null || wordDict.get(tempStr).size() == 0){
                    continue;
                }
                for(String getWord: wordDict.get(tempStr)){
                    if (getWord.equals(endWord)){
                        return getLevel + 1;
                    }
                    if (!hasVisit.get(getWord)){
                        queue.offer(new HashMap<>(){{put(getWord, getLevel + 1);}});
                        hasVisit.put(getWord, true);
                    }
                }
            }
        }
        return 0;

    }
}

代码2

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        if (beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0 || wordList == null || wordList.size() == 0){
            return 0;
        }
        Map> wordDict = new HashMap<>();
        Map beginVisit = new HashMap<>();
        Map endVisit = new HashMap<>();
        Queue beginQueue = new LinkedList<>();
        Queue endQueue = new LinkedList<>();
        
        beginVisit.put(beginWord, 1);
        endVisit.put(endWord, 1);
        beginQueue.offer(beginWord);
        endQueue.offer(endWord);
        boolean hasEndWord = false;
        
        for(String word: wordList){
            int l = word.length();
            if (word.equals(endWord)){
                hasEndWord = true;
            }
            for(int i = 0; i < l; i++){
                String tempStr = word.substring(0, i) + "*" + word.substring(i + 1, l);
                if (!wordDict.containsKey(tempStr)){
                    wordDict.put(tempStr, new ArrayList());
                }
                List tempList = wordDict.get(tempStr);
                tempList.add(word);
                wordDict.put(tempStr, tempList);
            }
        }
        System.out.println(hasEndWord);
        if (!hasEndWord){
            return 0;
        }
        
        while(!beginQueue.isEmpty() && !endQueue.isEmpty()){
            int getSame = updateQueue(wordDict, beginQueue, beginVisit, endVisit);
            if (getSame != -1){
                return getSame;
            }
            getSame = updateQueue(wordDict, endQueue, endVisit, beginVisit);
            if (getSame != -1){
                return getSame;
            }
        }
        return 0;
    }
    
    private int updateQueue(Map> wordDict, Queue queue, Map visit, Map visit1){
        String getStr = queue.remove();
        int l = getStr.length();
        int getLever = visit.get(getStr);
        for(int i = 0; i < l; i++){
            String tempStr = getStr.substring(0, i) + "*" + getStr.substring(i + 1, l);
            if (!wordDict.containsKey(tempStr) || wordDict.get(tempStr).size() == 0){
                continue;
            }
            for(String getWord: wordDict.get(tempStr)){
                if (!visit.containsKey(getWord)){
                    if (visit1.containsKey(getWord)){
                        return getLever + visit1.get(getWord);
                    }
                    queue.offer(getWord);
                    visit.put(getWord, getLever + 1);
                }
            }
        }
        return -1;
    }
}

复杂度分析

思路1时间复杂度

$O(m*n)$遍历完m个字符长度的n个词

思路1空间复杂度

$O(m*n)$存储可变换状态

思路2时间复杂度

$O(m*n)$遍历完m个字符长度的n个词

思路2空间复杂度

$O(m*n)$存储可变换状态