word ladder這道題是我2月份準(zhǔn)備面試時(shí)候非常怕碰到的考題哑舒。
因?yàn)橐蟮膐utput是最短transformation。所以幻馁，可以理解為求從A--B的最短距離洗鸵，使用BFS。
Example的 tree的形狀:?
但是我做這道題時(shí)候的一個(gè)非常錯(cuò)誤的點(diǎn)在于仗嗦，我把這個(gè)想的還是簡(jiǎn)單了一點(diǎn)膘滨。。稀拐。火邓。
我用了一個(gè)int level， 來(lái)記錄從Root到終點(diǎn)的路程：也就是經(jīng)過(guò)了幾個(gè)level德撬。 然后用了一個(gè)priority-Queue, 把節(jié)點(diǎn)放進(jìn)去铲咨。 比如說(shuō)：hit, hot, lot, dot, log, dog,...
但是這么做的問(wèn)題是當(dāng)我一個(gè)一個(gè)pop出來(lái)的時(shí)候，我不知道我自己在第幾個(gè)level蜓洪。
比如說(shuō)lot pop出來(lái)的時(shí)候 它以為自己是level3纤勒， 但是dot 下一個(gè)pop出來(lái)他也許會(huì)以為自己是level 4 因?yàn)槲覀儎倓偨olot pop 出來(lái)以后馬上加了一個(gè)level。這樣就會(huì)導(dǎo)致我們實(shí)際會(huì)多count 路程隆檀。但是這個(gè)問(wèn)題我是不知道有什么簡(jiǎn)單的解決方案摇天。。
正確的姿勢(shì)應(yīng)該是用一個(gè)hashSet把一層的node放進(jìn)去恐仑。 然后進(jìn)入下一層的時(shí)候泉坐， 讓cur_set=hashset，然后一個(gè)一個(gè)process里面的node菊霜，加入到新的hashset坚冀。
Edit on 8月13號(hào)：
今天看basketwang, 對(duì)這題的理解上升到了一個(gè)前所未有的高度。
我們可以一開始用一個(gè)先構(gòu)建一個(gè)Graph一樣的map鉴逞。每個(gè)node的neighbor放到map<node, neighbor> ?Neighbor的判斷就是判斷有沒(méi)有辦法通過(guò)改變當(dāng)前String的一個(gè)character得到一個(gè)String 在directory List 里记某。
然后BFS從第一個(gè)start word開始遍歷它的neighbor. 注意的是要用一個(gè)set來(lái)記錄去過(guò)哪里了別走回頭路！
我自己做了一遍卡在了BFS中如何判斷當(dāng)前在哪個(gè)level
發(fā)現(xiàn)這個(gè)太酷了构捡！用queue的size作為for limit.
這個(gè)是我目前為止寫的最酷的一次液南！
