Word Ladder II @Lintcode

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Have you met this question in a real interview? 

Yes

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

这道题写起来长，但其实一点都不难。只要领悟以下几个关键点：

1 因为要找最短路径，所以果断用bfs

2 要求返回所有可能的解，所以要记录层数，直到把最短路径答案所在的那一层全部试过为止

3 每个最终解都是一个path，每个节点都指向他的上一层。所以最好自己建一个数据结构

4 用过一个中间string就把它从dict里删除，因为最短路径里不可能包含一个重复的string

另外自己写code中会碰到很多可以优化的地方，所以最好还是自己写一遍哦 ^_^