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之間聯(lián)系，單詞如果只差一個單詞不同，則認(rèn)為這兩個單詞有聯(lián)系，這么看：這個題就是圖的問題。首先，建模成圖， 2. 然后這個題，就演變成遍歷圖，找到從hit到log的最短距離。這里用bfs求最小距離。 3. 這道題有兩種實現(xiàn)方式：第一種先把圖建立起來，即：對每個節(jié)點找到其neighbor,并對每個節(jié)點保存neighbor，然后從開始的位置，一層一層遍歷圖，知道找到結(jié)束的位置；第二種是一邊遍歷圖，一邊建立圖，即：首先根據(jù)開始的位置，去給定的unordered_set中找到和他相差一個字母的所有string,然后放在queue后面，然后繼續(xù)遍歷，從queue中取出一個string，然后有去這個unordered_set中找相差一個字母的所有string，放在queue后面。注意看，整個過程兩個階段是交叉進(jìn)行的，取一個節(jié)點，再找其全部neighbor，然后在取一個節(jié)點，再找這個點的neighbor。這個方法和第一種，先全部找到所有節(jié)點的neighbor再去遍歷相比，好處很明顯：如果某一個問題總的節(jié)點很多，而需要遍歷的節(jié)點很少，那么首先對全圖找所有節(jié)點neighbor就顯得效率很低，很多節(jié)點用不上，但也找了他們的neighbor。所以，一邊遍歷，一邊找neighbor的方法就很高效，動態(tài)的按需要去找neighbor! 4. 再上升一下，很多問題都可以因此而得到優(yōu)化，把一個大問題分解成兩個小問題，簡單粗暴的做法可能就是一個問題解決完全再解決另一個問題，但這樣就導(dǎo)致整個問題的解決過程是靜態(tài)的，效率也就低下；相反，如果把解決問題的幾個步驟shuffle，即：交叉進(jìn)行，或迭代進(jìn)行，整個解決過程就是動態(tài)的，考慮了問題實際復(fù)雜情況的一種方式，因此是高效的! 5. 最后，由于是無向圖，所以每個節(jié)點的neighbor在找neighbor時又會找到他自身。為了解決這個問題，通常有兩種方法：一種是用一個visited的vector來標(biāo)志某一個節(jié)點是否被訪問，如果已經(jīng)被訪問，就直接skip；另一個方法是：每次unordered_set中的數(shù)據(jù)訪問(添加queue)后，就直接刪除，也一樣可以解決問題！觀察這兩個方法，也很有意思。第一種方法是添加輔助的信息來分辨是否訪問過，第二種則是直接刪除訪問過的，這樣留下來的都是沒訪問過的。這一個添加、一個刪除都達(dá)到了相同效果，區(qū)別是:添加的原因，是assume不能修改原始數(shù)據(jù)，所以就只有加標(biāo)志位；刪除的原因，就是破除了這個假設(shè)。所以，刪除顯得更高級、更簡潔，不受潛意識的假設(shè)影響，或說打破了潛意識的這個假設(shè)。 6. 最后的最后，還要啰嗦一下，找neighbor時，簡單粗暴的方法是：把每個string和所有其他的string對比，看是否相差一位，這樣的復(fù)雜度就是o(nm)(m為string長度，n為string個數(shù))。這樣的方法有啥毛病嗎？肯定有了。試分析如下：首先每個string都是小寫字母，那么給定一個單詞，可能的neighbor只有26m個。更具體的說，一旦給定了string，其neighbor的集合也就隨之而固定，其neighbor就只有在這個集合里選。所以，方法就是每次只讓一位char從a到z枚舉，看這個變化的單詞是否出現(xiàn)在unordered_set，枚舉完所有的26m個可能即可。 7. 上面的方法和簡單粗暴的比，即使思維的革命：簡單粗暴的做法是沒考慮到搜索是在一個有限集合進(jìn)行，而且這個有限的集合比能看到的集合小。思維革命，就是不能只看眼前看得到的信息，還有看不見的被遮住的信息，比如：26m大小的有限集合！

//方法1：bfs求最短距離，用queue來保存每一層的節(jié)點。 class Solution { public:

}; “`