摘要：題目要求相比于，要求返回所有的最短路徑。至于如何生成該有向圖，則需要通過廣度優(yōu)先算法，利用隊列來實現(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ù)往下看之前，請先參考I的這篇博客
首先我們再來查看一下題目中的例子。其實我們可以將路徑化為有向圖，然后將有向圖中從beginWord至endWord的最短路徑全部枚舉出來。這里需要考慮最合適的數(shù)據(jù)結(jié)構(gòu)。graph的話我們通過Map>來記錄節(jié)點和從該節(jié)點出發(fā)可以到達的其它節(jié)點。在題中的含義也就是s1所能轉(zhuǎn)換的所有s2。至于如何生成該有向圖，則需要通過廣度優(yōu)先算法，利用隊列來實現(xiàn)。將每一層的string分別入棧。如果遇到endWord則至該層結(jié)尾廣度優(yōu)先算法結(jié)束。
這里有一個可以提高的計算效率的數(shù)據(jù)結(jié)構(gòu)。在一開始，我通過一個list來記錄所有上層已經(jīng)遍歷過的string。通過這種方式來防止形成圈。但是這樣的形式造成的代碼的超時，所以換成了Map來記錄String的最低層數(shù)。
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ā)技術，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/67615.html
