https://leetcode.com/problems/word-ladder-ii/
不是特别难的题目，但是对于BFS过程的路径记录，算是一个比较好的实现参考，有时候知道咋回事，但不能很快写出来。

个人解答

  1. class Solution:
  2.     def findLadders(self, a: str, b: str, wl: List[str]) -> List[List[str]]:
  3.         remain = set(wl)
  4.         q = {
  5.             a: [[a,]]
  6.         }
  7.         res = []
  9.         while q:
  10.             qq = collections.defaultdict(list)
  11.             for x in q:
  12.                 if x == b:
  13.                     res += q[x]
  14.                     continue
  15.                 for c in string.ascii_lowercase:
  16.                     for i in range(len(x)):
  17.                         w = x[:i] + c + x[i + 1:]
  18.                         if w in remain:
  19.                             qq[w] += [prev + [w] for prev in q[x]]
  20.             remain -= set(qq.keys())
  21.             q = qq
  23.         return res

题目分析

题目解法没什么好说的，基本上BFS可以解决，逐层拓展所有可能的情况，然后自然得出最短的路径。
重点在于，如何保存这个过程呢，DFS时，可以用一个数组来记录，BFS呢？

其实，很暴力，就，为每一个记录一个数组。

具体来看，就是题目中原来的queue，换成了一个dict，key是原来的值，value是key对应的list结果，如此一来，就可以通过值来得到对应的路径数组。

虽然暴力，但实现简单，而且，好像也没有什么好方法。

另外，本题需要注意两点：

  • 不能对于每个key判断后就把它标记为visited，因为可能在同一层，有其它的也可以获取到它
  • 为什么不用考虑长度超过最短的呢？因为BFS以及标记visited（remain）的缘故，结束符都不在了，就不会包含进来了，不过也可以标记遇到之后，下一轮就提前终止