【LeetCode】 20 单词接龙 II

题目

给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:

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

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

示例1:

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

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

示例2:

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

输出: []

解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。

思路

BFS
思路说明:在到达最短路径所在的层时,记录并输出所有符合条件的路径。

1.在单词接龙的基础上,需要将找到的最短路径存储下来;
2.之前的队列只用来存储每层的元素,那么现在就得存储每层添加元素之后的结果:"ab","if",{"cd","af","ib","if"};
(1)第一层:{"ab"}
(2)第二层:{"ab","af"}、{"ab","ib"}
(3)第三层:{"ab","af","if"}、{"ab","ib","if"}
3.如果该层添加的某一个单词符合目标单词,则该路径为最短路径,该层为最短路径所在的层,但此时不能直接返回结果,必须将该层遍历完,将该层所有符合的结果都添加进结果集;
4.每层添加单词的时候,不能直接添加到总的已访问单词集合中,需要每层有一个单独的该层访问的单词集,该层结束之后,再会合到总的已访问单词集合中,原因就是因为3.

代码

package com.janeroad;


import java.util.*;

public class test8 {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    // 结果集
    List<List<String>> res = new ArrayList<>();
    Set<String> distSet = new HashSet<>(wordList);
    // 字典中不包含目标单词
    if (!distSet.contains(endWord)) {
        return res;
    }
    // 已经访问过的单词集合:只找最短路径,所以之前出现过的单词不用出现在下一层
    Set<String> visited = new HashSet<>();
    // 累积每一层的结果队列
    Queue<List<String>> queue= new LinkedList<>();
    List<String> list = new ArrayList<>(Arrays.asList(beginWord));
    queue.add(list);
    visited.add(beginWord);
    // 是否到达符合条件的层:如果该层添加的某一单词符合目标单词,则说明截止该层的所有解为最短路径,停止循环
    boolean flag = false;
    while (!queue.isEmpty() && !flag) {
        // 上一层的结果队列
        int size = queue.size();
        // 该层添加的所有元素:每层必须在所有结果都添加完新的单词之后,再将这些单词统一添加到已使用单词集合
        // 如果直接添加到 visited 中,会导致该层本次结果添加之后的相同添加行为失败
        // 如:该层遇到目标单词,有两条路径都可以遇到,但是先到达的将该单词添加进 visited 中,会导致第二条路径无法添加
        Set<String> subVisited = new HashSet<>();
        for (int i = 0; i < size; i++) {
            List<String> path = queue.poll();
            // 获取该路径上一层的单词
            String word = path.get(path.size() - 1);
            char[] chars = word.toCharArray();
            // 寻找该单词的下一个符合条件的单词
            for (int j = 0; j < chars.length; j++) {
                char temp = chars[j];
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    chars[j] = ch;
                    if (temp == ch) {
                        continue;
                    }
                    String str = new String(chars);
                    // 符合条件:在 wordList 中 && 之前的层没有使用过
                    if (distSet.contains(str) && !visited.contains(str)) {
                        // 生成新的路径
                        List<String> pathList = new ArrayList<>(path);
                        pathList.add(str);
                        // 如果该单词是目标单词:将该路径添加到结果集中,查询截止到该层
                        if (str.equals(endWord)) {
                            flag = true;
                            res.add(pathList);
                        }
                        // 将该路径添加到该层队列中
                        queue.add(pathList);
                        // 将该单词添加到该层已访问的单词集合中
                        subVisited.add(str);
                    }
                }
                chars[j] = temp;
            }
        }
        // 将该层所有访问的单词添加到总的已访问集合中
        visited.addAll(subVisited);
    }
    return res;
}

public static void main(String[] args) {
    List<String> stringList = new LinkedList<String>(){{
        add("hot");
        add("dot");
        add("dog");
        add("lot");
        add("cog");
    }};
    test8 test8=new test8();
    System.out.println(test8.findLadders("hit","cog",stringList));
}
}

涉及到的知识点

List<String> stringList = new LinkedList<String>(){{
    add("a");
    add("b");
    add("c");
}};
  • List方法与set方法的区别

(1)重复对象

list方法可以允许重复的对象,而set方法不允许重复对象

(2)null元素

list可以插入多个null元素,而set只允许插入一个null元素

(3)容器是否有序

list是一个有序的容器,保持了每个元素的插入顺序。即输出顺序就是输入顺序,而set方法是无序容器,无法保证每个元素的存储顺序,TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序

image.png

(4)常用的实现类

list方法常用的实现类有ArrayList、LinkedList 和 Vector。其中ArrayList 最为流行,它提供了使用索引的随意访问,而LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适,Vector 表示底层数组,线程安全

Set方法中最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap实现的 HashSet;TreeSet 还实现了 SortedSet 接口,因此 TreeSet 是一个根据其 compare() 和compareTo() 的定义进行排序的有序容器

image.png

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×