【宽度优先遍历BFS】Leetcode127. 单词接龙

127. 单词接龙

这是一道典型的宽度优先遍历的题目。总结思路如下：
· 起点为beginWord，结束为endWord
· 每一次我都是在wordList中做选择，所以每次能够满足与前一个word字母只相差一个的时候加入队列，直到找到与endWord相等就是我们需要的答案

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 广度优先遍历Queue<String> queue = new LinkedList<String>(); // 队列queue.offer(beginWord); // 将起始word加入队列中，以此作为起点进行宽度搜索int res = 0; // 存放结果boolean[] wordIsAdd = new boolean[wordList.size()]; // wordIsAdd[i]表示wordList[i]是否已经加入过队列中，如果已经加入过，则跳过以减少搜索次数。while (!queue.isEmpty()) {int size = queue.size();res++; // 每走到此处，说明已经加入的word是转化中的一个中间步骤，所以res+1for (int i = 0; i < size; ++i) {String tmpStr = queue.poll(); // 出队列一个字符串，在这个字符串的基础上去找到与其相差一个字符的字符串加入到队列中if (tmpStr.equals(endWord)) { // 此时表示已经找到了wordList中与endWord相等的，即找到答案return res;}for (int j = 0; j < wordList.size(); ++j) {if (!wordIsAdd[j] && IsCanAddWord(tmpStr, wordList.get(j))) {queue.offer(wordList.get(j)); // 加入队列wordIsAdd[j] = true; // 将加入队列的word标识为已经加入过队列中}}}}return 0;}// 判断nextWord能否满足转换条件：与word只相差一个字母public boolean IsCanAddWord(String word, String nextWord){int numOfNotSame = 0;int size = word.length();for (int i = 0; i < size; ++i) {if (word.charAt(i) != nextWord.charAt(i)) {numOfNotSame++;}if (numOfNotSame > 1) {return false;}}return true;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！