Problem#
一個字串能夠從 beginWord 轉換成 endWord 稱作 transformation sequence
e.g. beginWord -> s1 -> s2 -> ... -> sk，今天題目給你一個 wordList 問你從 beginWord 到 endWord 總共幾個字串，並且要最短的。
- 其中每個字串只差一個字元 => 相差一個字元才能轉換
- 轉換的字串都在
wordList裏頭 beginWord不一定要在wordList裏頭
想法#
可以把每個 word 都想成圖上的 node，字串轉換就變成的從圖上的一個點移動到另一個點，
問題就變成想辦法建圖，從 beginWord 開始 bfs 即可。
對於每個字來說 e.g. dog，有三條路可以走: .og, d.g, do.，可以先建個 dictionary 來方便查找 e.g. .og = {dog, log, cog}，
接著就遍歷 wordList 把圖建起來。
小細節是 beginWord 要等圖建好之後，再連到圖上(單向)，這樣才不會走回去。
- 時間複雜度:
N = wordList.size(),M = wordList[i].size()(字串長度)- 建字串表: $\mathcal{O}(N)$
- 建圖: $\mathcal{O}(N^ \cdot M \cdot N)$
- BFS: $\mathcal{O}(N^2)$ (網狀圖)
- 空間複雜度: $\mathcal{O}(N^ \cdot M \cdot N)$
AC Code#
賞析#
TODO
心得#
一開始跟朋友討論時想複雜了= = (inspired by 祥恩)，後來看題解才知道有更簡單的解法