前往
大廳
主題

LeetCode - 127. Word Ladder 解題心得

Not In My Back Yard | 2022-09-20 12:00:01 | 巴幣 0 | 人氣 215

題目連結:


題目意譯:
藉由一個字典 wordList 從字詞 beginWord 轉到字詞 endWord 的一個變換序列為一個字詞之序列 beginWord → s1 → s2 → …… → sk 使得
每個相鄰之字詞對只有一個字元相異。
對於 1 ≦ i ≦ k 的每個 si 皆存在於 wordList 中。注意 beginWord 可以不必出現於 wordList 中。
sk == endWord

給定兩個字詞 beginWord 和 endWord 以及一個字典 wordList,回傳在從 beginWord 變到 endWord 的最短變換序列中存在的字詞數。如果不存在這樣子的序列則回傳 0。

限制:
1 ≦ beginWord.length ≦ 10
endWord.length == beginWord.length
1 ≦ wordList.length ≦ 5000
wordList[i].length == beginWord.length
beginWord 、 endWord 和 wordList[i] 由小寫英文字母組成。
beginWord != endWord
wordList 中的字詞皆相異。



範例測資:
範例 1:
輸入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
輸出: 5
解釋: 其中一個最短的變換序列為 "hit" -> "hot" -> "dot" -> "dog" -> cog",其為 5 個字詞長。

範例 2:
輸入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
輸出: 0
解釋: 結尾字詞 "cog" 不在 wordList 中,因此沒有任何合法的變換序列。


解題思維:
這題的簡化版,本題只需要求序列的長度即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作