資訊專(zhuān)欄INFORMATION COLUMN
題目：
Given two words (beginWord and endWord), and a dictionary"s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]
]
解答：
public class Solution {
List> result;
List list;
Map> map;
public List> findLadders(String beginWord, String endWord, Set wordList) {
result = new ArrayList>();
if (wordList.size() == 0) return result;
list = new LinkedList();
map = new HashMap>();
int curt = 1, next = 0;
boolean found = false;
Set unvisited = new HashSet(wordList);
Set visited = new HashSet();
Queue queue = new ArrayDeque();
queue.add(beginWord);
unvisited.add(endWord);
unvisited.remove(beginWord);
//BFS
while (!queue.isEmpty()) {
String word = queue.poll();
curt--;
for (int i = 0; i < word.length(); i++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = "a"; ch <= "z"; ch++) {
sb.setCharAt(i, ch);
String newWord = sb.toString();
if (unvisited.contains(newWord)) {
if (visited.add(newWord)) {
next++;
queue.add(newWord);
}
if (!map.containsKey(newWord)) {
map.put(newWord, new LinkedList());
}
map.get(newWord).add(word);
if (newWord.equals(endWord) && !found) found = true;
}
}
}
if (curt == 0) {
if (found) break;
curt = next;
next = 0;
unvisited.removeAll(visited);
visited.clear();
}
}
backTrace(endWord, beginWord);
return result;
}
public void backTrace(String word, String beginWord) {
if (word.equals(beginWord)) {
list.add(0, beginWord);
result.add(new ArrayList(list));
list.remove(0);
return;
}
list.add(0, word);
if (map.get(word) != null) {
for (String s : map.get(word)) {
backTrace(s, beginWord);
}
}
list.remove(0);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65031.html
摘要：題目要求相比于，要求返回所有的最短路徑。至于如何生成該有向圖，則需要通過(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...
摘要：存放過(guò)程中的所有集合為所有的結(jié)尾，則順序存放這個(gè)結(jié)尾對(duì)應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的，在下一個(gè)循環(huán)再依次對(duì)其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新，再將放入，并將鍵值對(duì)放入，進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...
摘要：題目解答主要解題思路的，把每一種可能的都放進(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...
摘要：另外，為了避免產(chǎn)生環(huán)路和重復(fù)計(jì)算，我們找到一個(gè)存在于字典的新的詞時(shí)，就要把它從字典中移去。代碼用來(lái)記錄跳數(shù)控制來(lái)確保一次循環(huán)只計(jì)算同一層的節(jié)點(diǎn)，有點(diǎn)像二叉樹(shù)遍歷循環(huán)這個(gè)詞從第一位字母到最后一位字母循環(huán)這一位被替換成個(gè)其他字母的情況 Word Ladder Given two words (beginWord and endWord), and a dictionary, find t...
摘要：但是這種要遍歷所有的情況，哪怕是已經(jīng)超過(guò)最小操作次數(shù)的情況，導(dǎo)致代碼超時(shí)。其實(shí)從另一個(gè)角度來(lái)說(shuō)，這道題可以看做是廣度優(yōu)先算法的一個(gè)展示。按上文中的題目為例，可以將廣度優(yōu)先算法寫(xiě)成以下形式。 題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...
閱讀 865·2023-04-26 00:30
閱讀 2780·2021-11-23 09:51
閱讀 1118·2021-11-02 14:38
閱讀 2775·2021-09-07 10:23
閱讀 2333·2021-08-21 14:09
閱讀 1539·2019-08-30 10:57
閱讀 1666·2019-08-29 11:20
閱讀 1209·2019-08-26 13:53
