資訊專欄INFORMATION COLUMN
摘要：使用，利用其按層次操作的性質(zhì)，可以得到最優(yōu)解。這樣可以保證這一層被完全遍歷。每次循環(huán)取出的元素存為新的字符串。一旦找到和相同的字符串，就返回轉(zhuǎn)換序列長(zhǎng)度操作層數(shù)，即。
Problem
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
Given:
start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
/* 考慮邊界情況，如果`dict`為空，或`start.equals(end)`，則不滿足`BFS`中循環(huán)的條件，在最后返回`0`. 如果是正常情況，`start`和`end`不等且`dict`包含轉(zhuǎn)換需要的階梯詞組，那么轉(zhuǎn)換次數(shù)加`2`，就是所求的轉(zhuǎn)換序列長(zhǎng)度。使用`BFS`，利用其按層次操作的性質(zhì)，可以得到最優(yōu)解。 **第一層while循環(huán)**：利用隊(duì)列先進(jìn)先出的原則，先用`size = q.size()`確定下一層`for`循環(huán)要從隊(duì)列取出`size`個(gè)元素。這樣可以保證這一層被完全遍歷。當(dāng)里面的三層`for`循環(huán)結(jié)束，即`q`的前`size`個(gè)元素全部遍歷過(guò)之后，操作次數(shù)`count++`. **第二層for循環(huán)**：對(duì)當(dāng)前這一層的`size`個(gè)元素進(jìn)行遍歷。每次循環(huán)取出的元素存為新的字符串`cur`。 **第三層for循環(huán)**：遍歷字符串`cur`的每個(gè)字符。 **第四層for循環(huán)**：將遍歷到的`cur`的第`i`個(gè)字符換成從`a`到`z`的26個(gè)字母，存為新字符串`word`。然后查找`dict`里是否包含`word`：若存在，則從`dict`中刪除此元素防止以后重復(fù)使用（無(wú)限循環(huán)），并將這個(gè)元素放入隊(duì)列`q`，用于下一層的`BFS`循環(huán)。一旦找到和`end`相同的字符串，就返回`轉(zhuǎn)換序列長(zhǎng)度 = 操作層數(shù) + 2`，即`count+2`。 */Solution Update 2018-9
class Solution {
public int ladderLength(String beginWord, String endWord, List wordList) {
Set dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return 0;
Set existed = new HashSet<>();
existed.add(beginWord);
int count = 1;
while (!existed.contains(endWord)) { //當(dāng)existed集合里包含了endWord，跳出while循環(huán)并返回步數(shù)count
Set wanted = new HashSet<>();
for (String s: existed) {
for (int i = 0; i < s.length(); i++) {
for (char ch = "a"; ch <= "z"; ch++) {
StringBuilder sb = new StringBuilder(s);
sb.setCharAt(i, ch);
String str = sb.toString(); //找到了下一個(gè)詞str
if (dict.contains(str)) { //如果下一個(gè)詞在dict里，從dict放入wanted
wanted.add(str);
dict.remove(str);
}
}
}
}
//此時(shí)existed中所有詞都找到了下一個(gè)詞的集合，存在wanted中
//如果wanted為空，則existed中的所有詞都不存在下一個(gè)變化，return 0
if (wanted.size() == 0) return 0;
//否則交換existed和wanted，步數(shù)count+1，繼續(xù)查找下一步變化
count++;
existed = wanted;
}
return count;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65773.html
摘要：當(dāng)遞歸到第次時(shí)，被調(diào)用了次。說(shuō)明整個(gè)已經(jīng)被找到，返回?；氐胶瘮?shù)，遍歷整個(gè)數(shù)組，當(dāng)函數(shù)返回時(shí)，才返回否則在循環(huán)結(jié)束之后返回。 Problem Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially a...
LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...
Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...
摘要：題目要求相比于，要求返回所有的最短路徑。至于如何生成該有向圖，則需要通過(guò)廣度優(yōu)先算法，利用隊(duì)列來(lái)實(shí)現(xiàn)。將每一層的分別入棧。如果遇到則至該層結(jié)尾廣度優(yōu)先算法結(jié)束。通過(guò)這種方式來(lái)防止形成圈。 題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...
摘要：題目解答主要解題思路的，把每一種可能的都放進(jìn)去試，看能不能有一條線邊到代碼當(dāng)然，這樣的時(shí)間還不是最優(yōu)化的，如果我們從兩頭掃，掃到中間任何一個(gè)能夠串聯(lián)起來(lái)都可以，如果沒(méi)有找到可以串聯(lián)的那么返回。 題目：Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...
閱讀 2058·2019-08-30 15:52
閱讀 2449·2019-08-29 18:37
閱讀 802·2019-08-29 12:33
閱讀 2849·2019-08-29 11:04
閱讀 1542·2019-08-27 10:57
閱讀 2102·2019-08-26 13:38
閱讀 2770·2019-08-26 12:25
閱讀 2459·2019-08-26 12:23
