【LeetCode】21单词接龙 I

题目

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

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

说明:

  • 如果不存在这样的转换序列,返回 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" 不在字典中,所以无法进行转换。

思路

https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/

代码

package com.janeroad;

import javafx.util.Pair;
import java.util.*;

public class test9 {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    // 由于所有单词的长度相同。
    int L = beginWord.length();
    // 字典,用于保存可以从任何给定单词组成的单词组合。通过一次更改一个字母
    Map<String, List<String>> allComboDict = new HashMap<>();

    wordList.forEach(
            word -> {
                for (int i = 0; i < L; i++) {
                    // Key is the generic word
                    // Value is a list of words which have the same intermediate generic word.
                    String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);
                    List<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<>());
                    transformations.add(word);
                    allComboDict.put(newWord, transformations);
                }
            });

    // BFS队列
    Queue<Pair<String, Integer>> Q = new LinkedList<>();
    Q.add(new Pair(beginWord, 1));

    // 访问以确保我们不会重复处理相同的单词。
    Map<String, Boolean> visited = new HashMap<>();
    visited.put(beginWord, true);

    while (!Q.isEmpty()) {
        Pair<String, Integer> node = Q.remove();
        String word = node.getKey();
        int level = node.getValue();
        for (int i = 0; i < L; i++) {

            // 当前单词的中间单词
            String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);

            // 下一个状态是共享相同中间状态的所有单词。
            for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                // 如果在任何时候找到了我们要寻找的东西
                // 即结尾词-我们可以返回答案。
                if (adjacentWord.equals(endWord)) {
                    return level + 1;
                }
                // 否则,将其添加到BFS队列。同时标记为已访问
                if (!visited.containsKey(adjacentWord)) {
                    visited.put(adjacentWord, true);
                    Q.add(new Pair(adjacentWord, level + 1));
                }
            }
        }
    }

    return 0;
}




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

评论

Your browser is out-of-date!

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

×