https://leetcode.com/problems/word-ladder/
Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:
For example,
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.
Note:
果然js不适合做题么，缺少各种通用方法。
这题挂了无数次啊，一开始错把入参当做Array，其实是个Set，之后就一直超时...
bfs的思路是没错的，但首先不能构造图，复杂度O(n^2) 肯定不行。
然后尝试直接在Set里找，找到一个删除一个，也是超时。
最后只能换成了现在的方式。
这道题test case有特殊性，dict里的单词不会特别长，但是数据量很大。
于是最终改成在bfs队列中出队一个元素，一个个地用a-z替换每个字母，然后去跟字典比较。
1 /** 2 * @param {string} beginWord 3 * @param {string} endWord 4 * @param {set<string>} wordDict 5 * @return {number} 6 */ 7 var ladderLength = function(beginWord, endWord, wordDict) { 8 var queue = []; 9 var i = 0; 10 queue.push(beginWord); 11 wordDict.delete(beginWord); 12 if(oneCharDiff(beginWord, endWord) && wordDict.has(endWord)){ 13 return 2; 14 }else{ 15 return bfs(); 16 } 17 18 function bfs(){ 19 var depth = 1; 20 while(queue.length > 0){ 21 depth++; 22 var count = queue.length; 23 while(count--){ 24 var curr = queue.shift(); 25 if(oneCharDiff(curr, endWord) && curr !== beginWord){ 26 return depth; 27 } 28 var needRemove = []; 29 for(var i = 0; i < curr.length; i++){ 30 for(var j = ‘a‘.charCodeAt(); j <= ‘z‘.charCodeAt(); j++){ 31 var testMatch = curr; 32 var ch = String.fromCharCode(j); 33 if(testMatch[i] !== ch){ 34 testMatch = replaceChat(testMatch, i, ch); 35 } 36 if(wordDict.has(testMatch)){ 37 queue.push(testMatch); 38 wordDict.delete(testMatch); 39 } 40 } 41 } 42 } 43 } 44 45 return 0; 46 } 47 function isStrInArr(str, arr){ 48 for(var i in arr){ 49 if(str === arr[i]){ 50 return true; 51 } 52 } 53 return false; 54 } 55 function replaceChat(source, pos, newChar){ 56 var sFrontPart = source.substr(0, pos); 57 var sTailPart = source.substr(pos + 1, source.length); 58 return sFrontPart + newChar + sTailPart; 59 } 60 function oneCharDiff(a, b){ 61 if(a.length !== b.length){ 62 return false; 63 } 64 var count = 0; 65 for(var i = 0; i < a.length; i++){ 66 if(a[i].toLowerCase() !== b[i].toLowerCase()){ 67 count++; 68 } 69 if(count >= 2){ 70 return false; 71 } 72 } 73 if(count === 1){ 74 return true; 75 }else{ 76 return false; 77 } 78 } 79 };
[LeetCode][JavaScript]Word Ladder
原文：http://www.cnblogs.com/Liok3187/p/4522369.html