[LeetCode] 127. Word Ladder

轉自LeetCode

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:

1. Only one letter can be changed at a time.
2. 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.

<Solution>

這題是很典型的 BFS 題目

code 如下
c++
上面這個解法會過，但是時間會比較久 可以利用 hash map 來做一些加速

思路如下

• 一樣使用到 BFS 的概念，但先把 wordList 轉換成 unordered_set，來加速判斷 word 是否在 list 裡

• 一樣使用一個 queue 來記錄該 word，以及到達該 word 的所需步數

• 對於每個 word 的每個位置，都做字母 a 到 z 的變化，來組成新的 word

• 看看新的 word 是否就是答案

• 如果不是答案，利用步驟一所產生的 hash map 來看新的word，是否存在 wordList 裡面。如果存在，就放到 queue 裡，預備做下一次檢查

code 如下(參考資料)
c++

kotlin
還有一個進化版的BFS解法

依然使用 hash map 來加速，但是這次改從兩端同時找起

核心想法是，如果能從 beginWord 變化到 endWord，那麼也能從 endWord 變化到 beginWord

其餘思路如下

• 準備兩個 set，以及兩個指標，分別指到 size 比較小的 set 和 size 比較大的 set

• 要區分大小 set 的原因也是用來加速，每次都只歷遍比較小的 set 去找答案

• 如果在比較小的 set 中的 word，可以變一個字就變成在比較大的 set 中的 word，這樣就代表找到答案了。因為兩個 set 分別從兩端來找，當一個 set 裡面的 word 可以變化成另外一個 set 裡面的 word 的時候，就是相遇點，代表可以把兩端給串起來

• 如果不在另一個 set 裡面，那就檢查變化後的 word 是否可用，可用的話就放到 nextReachableSet，最後在和 smallerSet 做 swap，用來進行下次的檢查

code 如下(參考資料)