word ladder這道題是我2月份準(zhǔn)備面試時候非常怕碰到的考題。

因為要求的output是最短transformation。所以，可以理解為求從A--B的最短距離，使用BFS。

Example的 tree的形狀:?

但是我做這道題時候的一個非常錯誤的點在于，我把這個想的還是簡單了一點。。。。

我用了一個int level， 來記錄從Root到終點的路程：也就是經(jīng)過了幾個level。 然后用了一個priority-Queue, 把節(jié)點放進去。 比如說：hit, hot, lot, dot, log, dog,...

但是這么做的問題是當(dāng)我一個一個pop出來的時候，我不知道我自己在第幾個level。

比如說lot pop出來的時候 它以為自己是level3， 但是dot 下一個pop出來他也許會以為自己是level 4 因為我們剛剛給lot pop 出來以后馬上加了一個level。這樣就會導(dǎo)致我們實際會多count 路程。但是這個問題我是不知道有什么簡單的解決方案。。

正確的姿勢應(yīng)該是用一個hashSet把一層的node放進去。 然后進入下一層的時候， 讓cur_set=hashset，然后一個一個process里面的node，加入到新的hashset。

Edit on 8月13號：

今天看basketwang, 對這題的理解上升到了一個前所未有的高度。

我們可以一開始用一個先構(gòu)建一個Graph一樣的map。每個node的neighbor放到map<node, neighbor> ?Neighbor的判斷就是判斷有沒有辦法通過改變當(dāng)前String的一個character得到一個String 在directory List 里。

然后BFS從第一個start word開始遍歷它的neighbor. 注意的是要用一個set來記錄去過哪里了別走回頭路！

我自己做了一遍卡在了BFS中如何判斷當(dāng)前在哪個level

發(fā)現(xiàn)這個太酷了！用queue的size作為for limit.

這個是我目前為止寫的最酷的一次！