单词接龙

力扣链接：127. 单词接龙

题目描述

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

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例

Java代码

class Solution {//BFS的思想public int ladderLength(String beginWord, String endWord, List<String> wordList) {Queue<String> queue = new LinkedList<String>();//少不了队列queue.add(beginWord);boolean[] marked = new boolean[wordList.size()+1];//少不了标记int layer = 1;//注意返回的是层数+1.所以这里直接放1了while(!queue.isEmpty()) {//固定的层数记录形式layer++;int size = queue.size();while (size-->0) {String cur = queue.poll();for (int i = 0; i < wordList.size(); i++) {if(marked[i])continue;String dic = wordList.get(i);if(canChange(dic, cur)) {if(dic.equals(endWord))return layer;queue.add(dic);marked[i] = true;}}}}return 0;}//是否可以转换的辅助函数public boolean canChange(String s,String t) {int len = s.length();int diff = 0;for (int i = 0; i < s.length(); i++) {if(s.charAt(i) != t.charAt(i))diff++;}return diff==1;}
}