[LeetCode] 126. Word Ladder II

轉自LeetCode

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• Return an empty list 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>

這題是 Word Ladder 的衍生題，難度提升了很多

一開始看到這題以為是要用 DFS 寫，但這題除了要求要找出變化過程，而且還是要最短的變化

因此還是得用 BFS 來解，不過得做一些變化才行

首先看第一種解法，用最基本的 BFS 來改

主要想法如下

• queue 改存 vector<string>，用來記錄整個變化過程

• 因為使用BFS，所以找到答案的時候，vector 的長度就是最短的。因此當後來的 vector 的長度比答案的長度還長的時候，就不需要繼續下去了

• 在還沒有找到答案之前，如果 vector 的長度比上一次的長，代表又多了一個字詞的變化，這時候可以把之前用過的字都從 set 裡面刪除，避免重複使用

• 其餘部分就和一般的 BFS 想法一樣

code 如下

和 Word Ladder 一樣，有更快的雙向 BFS 解法(可參考 Word Ladder 的說明)

想法如下

• 一樣準備兩個 set，分別是 headSet 和 tailSet，代表從頭的方向開始，以及從尾的方向開始

• 再多準備兩個 multi_map<string, vector<string>>，用來記錄每個 word 是怎麼變化過來的

• 因為每次歷遍，都是用 size 比較小的 set 來做，所以並不會知道目前是從頭開始的方向，還是從尾開始的方向，因此多用一個變數來記錄，這樣在插入新的 word 的時候，才能知道插入的順序性

• 因為使用 multi_map，代表同一個 key 可能有多個 value，所以使用 equal_range 來找到所有符合的 value

• 每次歷遍完 smallerSet 之後，在換成 nextReachableSet 之前，把用過的 words 和不再需要的 map value，都刪除掉，以加快之後的速度

code 如下