Leetcode 127. Word Ladder

Given two Words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. UPDATE (2017/1/20): The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

s思路： 1. 看到本题，要找word之间联系，单词如果只差一个单词不同，则认为这两个单词有联系，这么看：这个题就是图的问题。首先，建模成图， 2. 然后这个题，就演变成遍历图，找到从hit到log的最短距离。这里用bfs求最小距离。 3. 这道题有两种实现方式：第一种先把图建立起来，即：对每个节点找到其neighbor,并对每个节点保存neighbor，然后从开始的位置，一层一层遍历图，知道找到结束的位置；第二种是一边遍历图，一边建立图，即：首先根据开始的位置，去给定的unordered_set中找到和他相差一个字母的所有string,然后放在queue后面，然后继续遍历，从queue中取出一个string，然后有去这个unordered_set中找相差一个字母的所有string，放在queue后面。注意看，整个过程两个阶段是交叉进行的，取一个节点，再找其全部neighbor，然后在取一个节点，再找这个点的neighbor。这个方法和第一种，先全部找到所有节点的neighbor再去遍历相比，好处很明显：如果某一个问题总的节点很多，而需要遍历的节点很少，那么首先对全图找所有节点neighbor就显得效率很低，很多节点用不上，但也找了他们的neighbor。所以，一边遍历，一边找neighbor的方法就很高效，动态的按需要去找neighbor! 4. 再上升一下，很多问题都可以因此而得到优化，把一个大问题分解成两个小问题，简单粗暴的做法可能就是一个问题解决完全再解决另一个问题，但这样就导致整个问题的解决过程是静态的，效率也就低下；相反，如果把解决问题的几个步骤shuffle，即：交叉进行，或迭代进行，整个解决过程就是动态的，考虑了问题实际复杂情况的一种方式，因此是高效的! 5. 最后，由于是无向图，所以每个节点的neighbor在找neighbor时又会找到他自身。为了解决这个问题，通常有两种方法：一种是用一个visited的vector来标志某一个节点是否被访问，如果已经被访问，就直接skip；另一个方法是：每次unordered_set中的数据访问(添加queue)后，就直接删除，也一样可以解决问题！观察这两个方法，也很有意思。第一种方法是添加辅助的信息来分辨是否访问过，第二种则是直接删除访问过的，这样留下来的都是没访问过的。这一个添加、一个删除都达到了相同效果，区别是:添加的原因，是assume不能修改原始数据，所以就只有加标志位；删除的原因，就是破除了这个假设。所以，删除显得更高级、更简洁，不受潜意识的假设影响，或说打破了潜意识的这个假设。 6. 最后的最后，还要啰嗦一下，找neighbor时，简单粗暴的方法是：把每个string和所有其他的string对比，看是否相差一位，这样的复杂度就是o(nm)(m为string长度，n为string个数)。这样的方法有啥毛病吗？肯定有了。试分析如下：首先每个string都是小写字母，那么给定一个单词，可能的neighbor只有26m个。更具体的说，一旦给定了string，其neighbor的集合也就随之而固定，其neighbor就只有在这个集合里选。所以，方法就是每次只让一位char从a到z枚举，看这个变化的单词是否出现在unordered_set，枚举完所有的26m个可能即可。 7. 上面的方法和简单粗暴的比，即使思维的革命：简单粗暴的做法是没考虑到搜索是在一个有限集合进行，而且这个有限的集合比能看到的集合小。思维革命，就是不能只看眼前看得到的信息，还有看不见的被遮住的信息，比如：26m大小的有限集合！

//方法1：bfs求最短距离，用queue来保存每一层的节点。 class Solution { public:

}; “`