当前仅显示指定条件回帖 [ 展开查看全部 ]
文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / word-ladder
文件大小:
693.00 B
下载地址:
文本预览:
## [Breadth-first search](http://en.wikipedia.org/wiki/Breadth-first_search)
Finding the shortest path via BFS.
* a level counter, plus one when level ends
* find a word in `dict` that can be jumped to, add it into queue
* using something like a set to keep the visited path away.
## Time Limited Note:
At first, I use an `isConnected` function to check if every word in `dict` connected to current word,
obviously, it will take `O(len(dict))` time.
Some testcases on leetcode have a very large dict, my code fail.
Then, I change to an `O(len(word))` time method, that is to replace each char in the current word and check if it is in the `dict`.
This way help me pass the testcases.
Finding the shortest path via BFS.
* a level counter, plus one when level ends
* find a word in `dict` that can be jumped to, add it into queue
* using something like a set to keep the visited path away.
## Time Limited Note:
At first, I use an `isConnected` function to check if every word in `dict` connected to current word,
obviously, it will take `O(len(dict))` time.
Some testcases on leetcode have a very large dict, my code fail.
Then, I change to an `O(len(word))` time method, that is to replace each char in the current word and check if it is in the `dict`.
This way help me pass the testcases.
点赞
回复
X