美文网首页
LeetCode:127. 单词接龙

LeetCode:127. 单词接龙

作者: alex很累 | 来源:发表于2022-08-25 15:53 被阅读0次

问题链接

127. 单词接龙

问题描述

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

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

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

提示:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

示例

输入: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" 不在字典中,所以无法进行转换。

解题思路

这道题我一开始直接广度优先搜索暴力解题,结果喜提“超出时间限制”......
我们可以对所有的单词的关联关系进行建图,然后再使用广度优先搜索(具体可以看题解)。

代码示例(JAVA)

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 0.如果endWord不在wordList中,直接结束
        if (!wordList.contains(endWord)) {
            return 0;
        }

        // 1.建图
        Map<String, Integer> map = new HashMap<>();
        List<List<String>> list = new ArrayList<>();
        wordList.add(beginWord);
        for (String word : wordList) {
            drawPicture(map, list, word);
        }
        // 2.广度优先搜索求解
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int res = 1;
        while (!queue.isEmpty()) {
            res++;
            int curSize = queue.size();
            for (int i = 1; i <= curSize; i++) {
                String str = queue.poll();
                int pos = map.get(str);
                for (String newStr : list.get(pos)) {
                    if (visited.add(newStr)) {
                        if (endWord.equals(newStr)) {
                            return res / 2 + 1;
                        }
                        queue.add(newStr);
                    }
                }
            }
        }
        return 0;
    }

    private void drawPicture(Map<String, Integer> map, List<List<String>> list, String word) {
        // 0.新增结点信息
        addNode(map, list, word);
        // 1.当前结点对应关系在list中的位置
        int pos = map.get(word);
        // 2.建立结点关联关系
        for (int i = 0; i < word.length(); i++) {
            StringBuilder newString = new StringBuilder(word);
            newString.setCharAt(i, '*');
            String newStr = newString.toString();
            addNode(map, list, newStr);
            int newStrPos = map.get(newStr);
            list.get(pos).add(newStr);
            list.get(newStrPos).add(word);
        }
    }

    private void addNode(Map<String, Integer> map, List<List<String>> list, String word) {
        // 0.有重复的,直接结束
        if (map.containsKey(word)) {
            return;
        }
        // 1.新建结点
        map.put(word, map.size());
        list.add(new ArrayList<>());
    }
}

执行结果

相关文章

网友评论

      本文标题:LeetCode:127. 单词接龙

      本文链接:https://www.haomeiwen.com/subject/uhywgrtx.html