126. Word Ladder II

题目:

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

  1. Only one letter can be changed at a time
  2. 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"]
]

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

链接: https//leetcode.com/problems/word-ladder-ii/

题解:

求所有最短路径...第一想法是先定义一个用adjacent list表示的图类,然后用Dijkstra求最短路径们。

再仔细想一想,我们现在应该有两条路,一条是在Word Ladder I的基础上改进, 另外一条是用一个不太一样的方法从头思考设计和解决。

先试试第一条,在Word Ladder I基础上改进。一个可能的解法基本步骤可能是:

    1. 按照Word Ladder I的方法,用BFS求最段路径
    2. 找到第一条最短路径的时候,不返回,继续计算Queue里这一层BFS其他结点,看是否能有其他最短路径。 因为在这一层找到了最短路径,所以长度是固定的,找完这一层就可以结束了,返回结果。
    3. 在每一层BFS的时候cache之前路径。对于 visited的处理,在每一层运算结束之后再统一更新visited,否则如果下一节点由这一层的多个节点共用,会出问题。  
    4. 如何保存已经访问过的节点。比如假设用 HashMap<String, List<String>>来保存下一节点与之前路径,假设有一条为 tex, {red,ted,tex},还有一条 tex,{red,rex,tex},这时就有了collision。所以可能只能储存前序的节点,并不能保存整个路径,除非额外做些处理,比如另外做数据结构,或者把路径做成 word + delimiter,然后比较的时候取split string得到的数组里的最后一个元素, 之类的。   
    5. 只存前序节点的话,最后的结果应该是在HashMap里的一条<endWord, List<String>>。 这样再从endWord开始对List<String>做一个DFS,应该就可以找到所要求的路径。

12:53AM,尝试完毕,可以作为一个解。要继续研究最优解法。终于AC了好高兴,基本算是做了整整一天。写的代码丑陋异常...一定要再优化优化。复杂度应该和1一样,不过代码里面用到了list的contains,也许会增加一些低阶量。

Time Complexity - O(min(26^L, size(wordList)), Space Complexity - O(min(26^L, size(wordList)),  L为 word length。

public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
List<List<String>> res = new ArrayList<>();
if(beginWord == null || endWord == null || wordList == null || wordList.size() == 0 || beginWord.equals(endWord))
return res;
if(wordList.contains(beginWord))
wordList.remove(beginWord);
if(wordList.contains(endWord))
wordList.remove(endWord); Queue<String> q = new LinkedList<>();
q.offer(beginWord);
int curLevel = 1, nextLevel = 0;
HashSet<String> visited = new HashSet<>();
HashSet<String> levelVisited = new HashSet<>();
HashMap<String, ArrayList<String>> wordChains = new HashMap<>();
boolean foundShortestPath = false; while(!q.isEmpty()) {
String word = q.poll();
curLevel--; for(int i = 0; i < word.length(); i++) {
char[] wordAsArray = word.toCharArray(); for(char j = 'a'; j <= 'z'; j++) {
wordAsArray[i] = j;
String newWord = String.valueOf(wordAsArray); if(newWord.equals(endWord)) { // found shortest path at this level
foundShortestPath = true; // flag to only process this level, then return
if(wordChains.containsKey(endWord)) {
if(!wordChains.get(endWord).contains(word))
wordChains.get(endWord).add(word);
} else {
ArrayList<String> preWords = new ArrayList<>();
preWords.add(word);
wordChains.put(endWord, preWords);
}
break;
} if(wordList.contains(newWord) && !visited.contains(newWord)) { //found edge to next node
q.offer(newWord);
if(wordChains.containsKey(newWord)) {
if(!wordChains.get(newWord).contains(word))
wordChains.get(newWord).add(word);
} else {
ArrayList<String> preWords = new ArrayList<>();
preWords.add(word);
wordChains.put(newWord, preWords);
}
nextLevel++;
levelVisited.add(newWord); //add the newWord to a temp visited HashMap
}
}
} if(curLevel == 0) {
if(foundShortestPath)
break;
curLevel = nextLevel;
nextLevel = 0;
for(String str : levelVisited) //update the global "visited"
visited.add(str);
levelVisited.clear();
}
} ArrayList<String> list = new ArrayList<>();
list.add(endWord);
getWordChains(res, list, wordChains, beginWord, endWord);
return res;
} private void getWordChains(List<List<String>> res, ArrayList<String> list, HashMap<String, ArrayList<String>> wordChains, String beginWord, String endWord) {
if(endWord.equals(beginWord)) {
res.add(new ArrayList<String>(list));
return;
}
ArrayList<String> curLevel= new ArrayList<>();
if(wordChains.containsKey(endWord))
curLevel = wordChains.get(endWord);
else
return; for(int i = 0; i < curLevel.size(); i++) {
String word = curLevel.get(i);
list.add(0, word);
getWordChains(res, list, wordChains, beginWord, word);
list.remove(word);
}
}
}

再试试第二条(刷下一遍时)

急需学习图的各种知识。WordLadder这种经典题目,Sedgewick的算法书和Mark Ellen Weiss的数据结构书里都有涉及,要多学多练。

题外话: 中午去SOHO和Justin谈了一下,他说有3个startup不错,一个是doubleclick前CEO做的,专门搞古董交易的startup。第二个是ADP sponsor的internal子公司,做得很像zenefits。第三个是一个做男士剃须刀的,有专门的厂家在德国,目标是在你需要刮胡子的时候快递新的刮胡刀上门。真的很有意思,broaden my vision。 下午继续回公司做事,要处理好和同事,上级的关系,要有耐心,不要急躁。

Reference:

http://baike.baidu.com/view/349189.htm

https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98

http://blog.csdn.net/v_july_v/article/details/6181485

http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Graph.java.html

http://www.cnblogs.com/springfor/p/3893529.html

http://blog.csdn.net/linhuanmars/article/details/23071455

上一篇:Strawberry Perl CPAN Install Module 安装 Module 方法


下一篇:alternaiate terms