花花酱 LeetCode 126. Word Ladder II - 刷题找工作 EP72

[@HuaHuaLeetCode]

LeetCode 127. Word Ladder I kzbin.info/www/bejne/rIizdKBsbrKGnNU

[@jamesqiu6715]

一题多解是最好的开阔思路的方式！谢谢花花老大的勤奋和坚持！！！

[@_daohang_5168]

51行和52行之间似乎应该加一句if (found) break; 否则过不了beginWord = "a", endWord = "c", dict = {"a", "b", "c"}这样的testcase.

[@rickli2108]

大佬 牛B啊啊啊啊啊啊啊啊

[@nathan_milan_blacksmith3926]

花花的讲解很棒。只是我对单广的时间复杂度有疑问，你的答案是不是太loose了。 BFS 时间复杂度一般的就是O(V+E）, here V is len(wordlist), each word's neighbor is o(len(word) * 26). so E should be o(V*26*len(word)),so BFS is just O(V+V*26*len(word)) which is O(len(wordlist)*len(word)). Plus the time for build path which is O(number of solutions). which can be ignored compared to BFS time cost. so total time complexity is O(len(wordlist)*len(word)). Plz correct me if I am wrong. Many thanks

[@颜巾斌]

这道题比较经典,总结下，BFS构建父子关系血缘图，然后用DFS查找可能的解

[@bartholdic4216]

想问问花花，在for (int j = 'a')这个循环中的else分支，为什么要判断step < steps.at(w)，如果是the same，难道不应该是

[@tianbingleng1835]

谢谢讲解！有一个问题想问下，就是第一种解法大约12min的时候，代码里面出现了两次parents[w].push_back(p) ，分别是40行和47行。那这样的话，如果是重复出现过的node但是有另外transform的情况是不是就加进Parent两次了？

[@chonglu3566]

不会，因为如果出现过了node我们的dict里面就已经把他删除了。这个时候在else语句里的parent加过之后会直接continue

[@wenyuewang5842]

这两个p是不一样的。47行加入的p 是 第一次碰到 w 时的 parent1。 40行加入的p 是 与之前 parent1 同一层的 parent 2

[@_daohang_5168]

在找到endWord的那个if branch结束处可以直接continue. 因为在一开始已经做过dict.erase(endWord). if (endWord==w) { parents[w].push_back(p); found = true; continue; // endWord is already erased at the beginning. } 所以两句parents[w].push_back(p) 不会在同一个iteration里同时被hit

[@zhendongma4645]

看comment， line40， 如果不是new word（这个word 已经从dict里面被删掉） 那么一定是不同的parent 所以要记录下来这个parent，应为dict里面已经没有这个word 所以到line43 就会跳出， 如果能继续到 line47 说明 是new word 所以要记录这个word 的parent

[@jasonswift7468]

3种方法都用Java语言试了一下，运行时间102ms, 82 ms, 22 ms。每种方法都90行左右。

[@kingofwebguru]

@Jason Swift 能分享你的Java code 嗎？ 謝！

[@mikezhu5894]

感谢花花, bidirectional BFS里面, dict 只要erase q1里面的东西就可以了.

[@yuehuang5639]

想请教huahua一个问题，如果把while循环改成for(; q.empty() == false && (!found); q.pop())， 然后原来while里面对queue的for循环删掉，这样写会漏掉一个解，自己实在想不通为啥，谢谢!

[@heisenchoi49]

能不能把老的视频放在播放列表排序的前面，方便连续播放。谢谢。

[@yingxie9974]

and in the middle, return res rather than res+1

[@leixia6415]

Huahua你好 ； 请问 (11:58): step< steps.at(w) : "步数比当前的步数小,就说明是同一层的上面的单词", 这是为什么呀？step< steps.at(w)这行直接翻译过来是当前的步数比较小，怎么就是“同一层上面”的呀？想了很久还是不懂，请求您的指点

[@xinzhang5877]

step< steps.at(w)的意思是，之前已经发现过到达w的path，但是length比较长，当前的step更短。举个例子已有path：begin->A->B->w，当前path，begin->C->w。这些path都会抵达w，所以说是到达w后是同一层。可以想象如果当前path最后会到endword，w是这之中的关键节点，有的path花更久到w，有的path很快就可以到w，后者将会是最短的path。不知道这样讲能否说清楚，希望能帮到。

[@FrankOnwood]

@@xinzhang5877 感谢解答，但是还是有一个问题，比如之前的path是begin->A->B->w，找到更短的begin->C->w，这时候W的parents就包含B和A了吧，因为之前发现B->W，会加到parents一次，现在发现C->w,又会加一次，怎么保证是最短的呢？

[@Donald_Trump001]

@@FrankOnwood 上面那个哥们说错了，因为是层序遍历，遍历到结果found就会为True，所以只能遍历到当前层，这样保证了是最短。至于step < steps.at(w)，这时候step的值其实是等于到达parent时候的step，也就是此时的step == parents[p]

[@Donald_Trump001]

@@xinzhang5877 如果出现了 begin -> c ->w，就不可能出现begin ->a -> b ->w，你说错了

[@zhulin2531]

@@Donald_Trump001 是等同于step + 1 == steps.at(w)吗

[@yingxie9974]

return res -1; rather than res because res++ when it goes into while, but there maybe no answer, in this case, res should be res -1;

[@walkmoon3479]

这道题真的是，当年怎么做，怎么超时。。。

[@favorite3784]

时间复杂度可以讲解一下吗？为什么是O(N*26^L)?

[@jieyin4169]

如果在44行从dict里面删除w, 那么从改行另一个p到w的路径不就 无法添加到路径吗，因为下次查找的时候在43行就continue了

[@jieyin4169]

*该行*

[@颜巾斌]

哈哈 终于知道花花酱 叫啥名字了 纯好奇😄

[@johnnyzhao2668]

谢谢花神

[@stillyi]

hahahahhaa 20:37 我两倍速听着然后重新切成1倍速确定是不是真的自己骂了一句自己

[@rickli2108]

花花牛B ！！！

[@jasonswift7468]

花花，p在swap后clear()了，为什么直接写 q = p; p.clear(); 答案是不对的？

[@HuaHuaLeetCode]

应该是可以的吧，只是q = p 会copy

[@kissinguramii]

感谢老大

[@rowen7071]

很好奇为啥127是一，126是二

[@HuaHuaLeetCode]

那得问leetcode了

[@avltree6036]

這題真TM有夠難

[@iriszheng3025]

nice

[@spiceEx]

kzbin.info/www/bejne/hpPPl4SombyLh5Y 为什么说”它是和我同一层的“。

[@spiceEx]

这个”我“指的是谁呢？

[@spiceEx]

某一层可以出现重复，但是不同的层不能有重复出现，因为出现在其他地方的话步数一定会变长。 这里又说在扩展时候发现了上一层同款元素，这不是违反了之前的规则吗？？

[@spiceEx]

可是把p添加到w里有什么意义？ 之后输出path的时候，w如果走p的分支，路径长度一定会+1,不会是最短路径，那记录它还有什么用处？

[@spiceEx]

这里如果有图解释一下就好了。

[@spiceEx]

kzbin.info/www/bejne/hpPPl4SombyLh5Y 这里明明写的是

[@慕容谷歌]

666

[@zhangsteven8032]

666