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:

}; “`