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

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

}; “`