摘要:題目要求相比于,要求返回所有的最短路徑。至于如何生成該有向圖,則需要通過廣度優(yōu)先算法,利用隊(duì)列來實(shí)現(xiàn)。將每一層的分別入棧。如果遇到則至該層結(jié)尾廣度優(yōu)先算法結(jié)束。通過這種方式來防止形成圈。
題目要求
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 transformed word must exist in the word list. Note that beginWord is not a transformed word. For example, Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log","cog"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Note: Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. Yo
u may assume beginWord and endWord are non-empty and are not the same.
相比于Word Ladder I,II要求返回所有的最短路徑。
思路與代碼在繼續(xù)往下看之前,請(qǐng)先參考I的這篇博客
首先我們?cè)賮聿榭匆幌骂}目中的例子。其實(shí)我們可以將路徑化為有向圖,然后將有向圖中從beginWord至endWord的最短路徑全部枚舉出來。這里需要考慮最合適的數(shù)據(jù)結(jié)構(gòu)。graph的話我們通過Map
這里有一個(gè)可以提高的計(jì)算效率的數(shù)據(jù)結(jié)構(gòu)。在一開始,我通過一個(gè)list來記錄所有上層已經(jīng)遍歷過的string。通過這種方式來防止形成圈。但是這樣的形式造成的代碼的超時(shí),所以換成了Map
public List> findLadders(String beginWord, String endWord, List
wordList) { Map ladder = new HashMap (); for(int i = 0 ; i q = new LinkedList (); int minStep = Integer.MAX_VALUE; if(beginWord!=null){ q.offer(beginWord); while(!q.isEmpty()){ String current = q.poll(); int step = ladder.get(current)+1; if(step>minStep) break; for (int i = 0; i < current.length(); i++){ StringBuilder sb = new StringBuilder(current); for (char ch="a"; ch <= "z"; ch++){ sb.setCharAt(i, ch); String sbs = sb.toString(); if(ladder.containsKey(sbs)){ if(step>ladder.get(sbs)) continue; else if(step list= new HashSet (); list.add(sbs); map.put(current,list); } if(sbs.equals(endWord)) minStep = step; } } } } } generatePath(beginWord, endWord, new ArrayList ()); return result; } public void generatePath(String currentWord, String endWord, List current){ current.add(currentWord); if(currentWord.equals(endWord)){ result.add(new ArrayList (current)); }else{ Set set = map.get(currentWord); if(set!=null){ for(String s : set){ generatePath(s, endWord,current); } } } current.remove(current.size()-1); }
想要了解更多開發(fā)技術(shù),面試教程以及互聯(lián)網(wǎng)公司內(nèi)推,歡迎關(guān)注我的微信公眾號(hào)!將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://hztianpu.com/yun/67615.html
摘要:存放過程中的所有集合為所有的結(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...
題目:Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a timeEach...
摘要:另外,為了避免產(chǎn)生環(huán)路和重復(fù)計(jì)算,我們找到一個(gè)存在于字典的新的詞時(shí),就要把它從字典中移去。代碼用來記錄跳數(shù)控制來確保一次循環(huán)只計(jì)算同一層的節(jié)點(diǎn),有點(diǎn)像二叉樹遍歷循環(huán)這個(gè)詞從第一位字母到最后一位字母循環(huán)這一位被替換成個(gè)其他字母的情況 Word Ladder Given two words (beginWord and endWord), and a dictionary, find t...
摘要:但是這種要遍歷所有的情況,哪怕是已經(jīng)超過最小操作次數(shù)的情況,導(dǎo)致代碼超時(shí)。其實(shí)從另一個(gè)角度來說,這道題可以看做是廣度優(yōu)先算法的一個(gè)展示。按上文中的題目為例,可以將廣度優(yōu)先算法寫成以下形式。 題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...
摘要:使用,利用其按層次操作的性質(zhì),可以得到最優(yōu)解。這樣可以保證這一層被完全遍歷。每次循環(huán)取出的元素存為新的字符串。一旦找到和相同的字符串,就返回轉(zhuǎn)換序列長度操作層數(shù),即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...
閱讀 3818·2021-11-25 09:43
閱讀 800·2021-09-22 15:59
閱讀 1885·2021-09-06 15:00
閱讀 1918·2021-09-02 09:54
閱讀 832·2019-08-30 15:56
閱讀 1310·2019-08-29 17:14
閱讀 1992·2019-08-29 13:15
閱讀 1019·2019-08-28 18:28