package leetcode.editor.cn;//给定两个单词（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" 不在字典中，所以无法进行转换。 
// Related Topics 广度优先搜索import java.util.*;//Java：单词接龙
public class P127单词接龙{public static void main(String[] args) {Solution solution = new P127单词接龙().new Solution();List<String> wordList = new ArrayList<>();String[] str = {"hot","dot","dog","lot","log"};for (int i = 0; i < str.length; i++) {wordList.add(str[i]);}int ans = solution.ladderLength("hit", "cog", wordList);// TO TEST}//leetcode submit region begin(Prohibit modification and deletion)class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Queue<String> queue = new LinkedList<>();boolean[] flag = new boolean[wordList.size()];queue.add(beginWord);int ans = 1;while (!queue.isEmpty()) {ans++;Queue<String> tempQueue = new LinkedList<>();for (String strTemp : queue) {for (int i = 0; i < wordList.size(); ++i) {String current = wordList.get(i);if (flag[i] || !oneDiff(strTemp, current)) {continue;} else if (current.equals(endWord)) {return ans;}flag[i] = true;tempQueue.add(current);}}queue = tempQueue;}return 0;}public boolean oneDiff(String one, String two) {char[] charsA = one.toCharArray();char[] charsB = two.toCharArray();int ans = 0;int len = charsA.length;for (int k = 0; k < len; k++) {if (charsA[k] == charsB[k]) {ans++;}}return ans == len - 1;}
}
//leetcode submit region end(Prohibit modification and deletion)}