花花酱 LeetCode 127. Word Ladder - 刷题找工作 EP71

[@bills5639]

花花酱你好。视频很棒，非常感谢。我这里有一个关于时间复杂度的问题。 拿单广为例,视频中时间复杂度是O(n*26^l).而长度为l的word所有组合的可能性是26^l。那么这26^l一定包含起始单词和结束单词。那么实际计算次数不应该超过26^l就可以得到这条从begin ->...->end的路径 而我的想法是，每一个单词得到它所有距离为1的单词（neighbor）的时间复杂度是O(26*l); 如果wordlist中有n个词，那么得到所有单词的neighbor的时间复杂度是O(n * 26 * l).而如果存在从begin 到end的通路，它一定这 n*26*l个结果中。这一过程也对应你代码中的两个for循环。所以时间复杂度应该是O(n*26*l) -> O(n*l).

[@HuaHuaLeetCode]

Good point and you're right. For each word in the queue (must from dict except the beginWord), we use two for loops to try all 26*l possible transformations, operations within inner loop is O(1), and there are at most (n + 1) words. So the total time complexity should be O(n*26*l) = O(n*l). Same for bidirectional BFS.

[@henryhardcore8584]

确实应该是26*l, 因为每次只换其中的一个字符

[@dongfangshuo1521]

b is width. 这个例子里面width等于26，指每一位有26个字母的可能性。d是深度。 虽然最后真正被展开的each word必定是从wordlist来，但是判断一个word是否属于wordlist也是需要花时间的，我感觉双向算法是在这里节省了时间，因为on average depth是原来的一半。双向算法里最重要的一行代码是 if (q1.size() > q2.size()) std::swap(q1, q2);, 这个能保证先展开小的一行，所以overhead节省很多。

[@BullishBuddy]

@@HuaHuaLeetCode 如果不是exponential的时间复杂度，那么bidirectional省时间体现在哪些环节呢？？

[@lulu2740]

时间复杂度是O(n*26^l)，每个单词有26^l可能，虽然只有最多n个word在下一个level，但每个单词26^l是固定的，只有n可能变化，但双向比单向的影响最多是倍数级的，在时间复杂度上没有什么影响

[@ruizhenmai1194]

给用python的同学提个醒，如果在queue里直接加string convert成的list一定要加deep copy

[@frankieyao1843]

谢谢花花，使用Java的小伙伴需要注意，从实现的角度来说，直接用题目给的wordList进行判断和删除操作就够了，但是从性能角度来说，它会超时，因为List的底层数据结构是数组，使用contains()方法的时间复杂度为O(n)，而HashSet的底层数据结构是数组+链表，JDK8 后调整为数组+链表+红黑树，大部分情况下contains()方法的时间复杂度为O(1)。

[@老谈]

嗯 时间复杂度应该是 O(n*l) where n is the number of words in word list and l is the the length of each word

[@yinghuahu]

Java 双广没有用最小的set扩展的时候91ms, 用了以后27ms, 这个trick的提高还挺多的。

[@ryanxie1359]

求问单向bfs时间复杂度为什么是n*26^L? 每次替换不应该是n*26*L吗？

[@xinhuang5501]

应该是 n * 26 * L * L 从char array 到string 这步要花掉o(L)

[@qiupeizhao6526]

我觉得双向bfs里面有一个潜在的bug，如果q1或者q2其中一个 为空（上一轮未发现可扩张的字符）那么根据短字符优先原理为零的set永远会被选中而成为死循环

[@luyisong6575]

不会啊。外面的大循环控制条件就是两个Set都不能为空：while(!q1.isEmpty() && !q2.isEmpty()).

[@futureguy]

这题比较坑的是很容易超时。一开始bfs直接用wordList进行for loop判断和删除，但是会超时。后来改成花花这个方法，一个character一个character换，勉强通过，不知道怎么再优化。

[@futureguy]

from collections import deque class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: # Breadth First Search n = len(beginWord) # Initializing a queue q = deque() word_set = set(wordList) if not endWord in word_set: return 0 step = 1 q.append(beginWord) while len(q) > 0: q_size = len(q) while q_size > 0: curr = q.popleft() if curr in word_set: word_set.remove(curr) q_size -= 1 for i in range(0, n): for ch in list(string.ascii_lowercase): temp = curr[:i] + ch + curr[(i+1):] if temp not in word_set: continue if temp == endWord: return step + 1 q.append(temp) step += 1 return 0

[@sallyzhangt]

感谢上传。但是我现在有点怀疑自己的中文能力了……………有些地方听不太懂………

[@spiceEx]

我也听不懂，比如这里 kzbin.info/www/bejne/rIizdKBsbrKGnNU “你是要 shichen?”出来一个图。

[@spiceEx]

打拼音的时候明白了，是“生成”的意思吧hhhh. 待会听不清的都写一遍拼音。

[@spiceEx]

这次视频很多 you know ，听到了夹杂英文 =_=

[@ruoxisun1849]

bidirectional BFS pseudo 中， 为什么s=s1 而不是 s.append(s1). 只保留最新level，之前level在q中的元素都不要了么？ 会不会之前的更快与另一端meet？

[@smartyeung8338]

花花酱你好, why there is only 'dot' in level 3, i think 'lot' also in level 3 too

[@intoeleven]

讲的很好，代码风格写的也真的挺好！双向bfs那有个地方想问一下，在从'a' 遍历到 'z' 的那个for loop时候，为什么不判断一下 (j == ch) continue; 也能ac？ 难道不会让下一层新queue里产生重复的新词吗？

[@lixin9884]

谢谢花花，视频很好。就是不是特明白为什么BFS能保证找到的是最短的路径？如果多条路径出现的话，比如在每一层，都有几个合法字符。

[@xicai2290]

因为BFS是一层层遍历（所有node都一起向外扩展）一旦有feasible path那么一定是optimal（shortest）path

[@MrOsirisDL]

语速有点快。关键词有点听不太清..关键的地方稍微放慢一点就好。。总的思路还是很清晰的。code很简洁，赞一个。

[@lafillerose1]

花花，双广有一点我没懂，就是在扩展set A时，我们会去检查这个扩展的单词是否在set B中。但是这个单词也许会在B的历史set中，我们就没法找了，这样就错过了两个set可能的更早的相遇。您能给解释一下吗，谢谢！

[@leonreno5968]

不会发生这种情况。你描述的情况是先发生扩展setB历史set，后发生扩展setA。在setB的那个历史set扩展之后, 该历史set里的所有词都会从wordlist去掉。 后面在扩展setA时因为这些词已经被从wordlist去掉了，所以不会再那个历史set扩展之后再生成出来。

[@DukeDqd]

风骚走线.....

[@Cc-ly8kq]

秋迪也是学cs的吗

[@qingzhong4892]

我靠惊现懂球帝。。。。。。。

[@sunnyday12131]

很清晰，谢谢！

[@Xin-dm1be]

花花 难道是延安人？有木有走进过延安门？

[@xiuwenzhong7375]

请问为什么要swap(s1, s2) ?

[@rongrongmiao4638]

这题不能用trie吗? 把word list做成trie是否可以在枚举bfs节点那块加速？

[@yanwugu]

所以bidirectional bfs复杂度是n*26*l／2，只有一半的node需要找邻居？

[@SundayWindy]

这个地方不应该是26的l次方吧，应该是26*l吧，应为每次只需要改变一位啊

[@botenjohn1752]

不是。。。2位二进制有几个组合? 00, 11, 01, 10, 即 2^2。那么本题，词长 l 而每个字符有26个字母可变，即 26^l

[@nathan_milan_blacksmith3926]

​@@botenjohn1752 这个明显不是组合问题。 组合问题比one-character-transform的超集。对于ab来说， one character-transform就是 bb,cb...zb. 和 aa, ac...az. 组合就多了去了，bc就是组合的一个，但不是one-chracter-transform. 从code也应该能看出来就是 two nested loops

[@yajingcai5820]

时间复杂度是不是有问题

[@dandanlin1871]

在双向BFS中， 可不可以直接把q1里的旧w 删除然后加入新的w? 省略swap(q, q1) 是否行得通？

[@weifeng0715]

既然时间复杂度在worse情况下那么高，为什么不直接检查wordlist呢

[@司曹龙]

您好，花花师兄 您的视频真好，不过您有源码么？收益匪浅

[@HuaHuaLeetCode]

源码都在 zxi.mytechroad.com/blog/searching/127-word-ladder/

[@iriswang6760]

谢谢讲解，请问从c++翻译成python是用什么软件翻译的吗？还是花花大神自己翻译的啊？

[@HuaHuaLeetCode]

手工翻译

[@belindamao8611]

为什么双广需要swap呀？不太明白这里

[@jmgrn61]

在leetcode上用for (int size=0; size0; size--) 竟然无法通过，请问这里有什么需要注意的吗？

[@csnoob7925]

q.size()每次會改變 放在第一格初始就不會受到之後改變的影響 不然不要在回圈裡宣告也行

[@sewelllyu2681]

这个风骚的走线

[@perlaz1166]

写得真好！比solution简洁

[@vincentzheng3042]

感谢花花

[@清风徐来-h8c]

return step + 1; / 为什么这里的 step 还要加 1呀？

[@ruoxisun1849]

谢谢花花！！ 不用dfs是因为bfs可以保证最短路径？

[@HuaHuaLeetCode]

是的, BFS能确保最短路径。DFS其实也可以用来找最短路径，不过需要使用IDS (en.wikipedia.org/wiki/Iterative_deepening_depth-first_search) ，效率稍微低一些。

[@ruoxisun1849]

谢谢花花！ 你的视频讲得都太清晰。我总希望不会的题能在你讲的list里！

[@bingwu3091]

@@HuaHuaLeetCode 感谢花花回复，这周的面试中遇到了这个问题，自己本来bfs和dfs都会写，但是面试紧张着急写了dfs，面试官让分析dfs复杂度的时候，半天分析不出来，我自己之后也想了一下，也没有一个合适的答案，能不能请花花指点一下dfs解法的复杂度？感谢

[@Emma-ru7kj]

每天都看 打卡

[@lilllllllllllll]

谢谢huahua酱！

[@清风徐来-h8c]

I change the unordered_set to set, and it takes more time to execute the code. Why?

[@HuaHuaLeetCode]

set is O(logn) unordered_set is O(1) ... when you have fewer keys (

[@jmgrn61]

@@HuaHuaLeetCode 记得题中有You may assume no duplicates in the word list.这个条件，所以应该不需要去重操作。那么请问一开始把wordList转化成unordered_set的目的是什么呢？是不是主要因为vector的“count()”与“erase()”函数比较难用，而unordered_set的相关操作非常方便？

[@weihanwang3203]

时间复杂度怎么分析 这题

[@vurtnesaerdna]

支持ni

[@jiaxinsun9444]

这题写了BFS没用HashSet一直TLE，气死...

[@xxqq96]

python是不是不能像C++那样直接修改字符串

[@HuaHuaLeetCode]

快zero老熊 python的string是immutbale的，需要先转成list才可以修改。

[@xxqq96]

@@HuaHuaLeetCode 谢谢花花 但是C++就可以直接对index的char进行修改是吧

[@HuaHuaLeetCode]

快zero老熊 可以的，c++的string就是个char数组…

[@diodin8587]

这个不应该用Dijkstra算法吗

[@a3090102735]

我一开始也是这么想的 可是仔细算了时间复杂度之后 这种特殊的unweighted graph其实BFS更快

[@GwendolynYang]

没太听清楚 branch factor -b 是什么？

[@GwendolynYang]

请问这里的b 是不是 26个字母。d是单词的长度。

[@AlvinC-sz3li]

如何保证是最小的路径呢

[@HuaHuaLeetCode]

当graph所有的边权重都是1，BFS能保证找到最短路径，如果存在的话

[@清风徐来-h8c]

why not just use set instead of unordered_set?

[@allenchen8559]

When we do dict.count(w) [line 32], it takes O(1) for unordered set cause unordered set is based on hash table. But set is based on red-black tree, it takes O(logN) to find an element.

[@yingjienatalieding1560]

花花酱 这个有java 版本不？

[@HuaHuaLeetCode]

Java 版本的单广和双广都加上了。 zxi.mytechroad.com/blog/searching/127-word-ladder/

[@HuaHuaLeetCode]

Bidirectional BFS Python code, faster than 96.84%: zxi.mytechroad.com/blog/searching/127-word-ladder/ LeetCode 126. Word Ladder II: kzbin.info/www/bejne/hpPPl4SombyLh5Y

[@Timepass_duniya]

What the Fuck is this ?