leetcode70，LeetCode 127. Word Ladder

2023-12-06 阅读 37 评论 0

摘要：原題鏈接在這里：https://leetcode.com/problems/word-ladder/ leetcode70。題目： 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:

原題鏈接在這里：https://leetcode.com/problems/word-ladder/

leetcode70。題目：

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:

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

題解：

用BFS找最短路徑。先把beginWord放入queue中，level 設值為1. 在queue不為空的情況下，從queue中拿出一個word, 設為cur, 同時curCount--.

從cur的第一個字母開始，從a 到 z 挨個替換，若是等于了endWord, 直接返回level+1即可。否則就看set 中是否有這個變形，若是有就把他添加到queue中，并增加計數nextCount. 為了保證不陷入infinite loop, 需同時從set中remove掉這個詞。

每當curCont == 0時，說明本層已經掃描完，level++, 同時更新curCount 為nextCount, nextCount 為 0.

Time Complexity: O(m*n). m = wordList.size(). n = beginWord.length().

Space: O(m). queue把所有的word都加了進去.

AC Java:

public class Solution {public int ladderLength(String beginWord, String endWord, Set<String> wordList) {if(beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0 || beginWord.length() != endWord.length()){return 0;}int level = 1;int curCount = 1;int nextCount = 0;LinkedList<String> wordQue = new LinkedList<String>();wordQue.offer(beginWord);while(!wordQue.isEmpty()){String cur = wordQue.poll();curCount--;for(int i = 0; i<cur.length(); i++){char [] curToChar = cur.toCharArray();for(char k = 'a'; k<='z'; k++){curToChar[i] = k;String check = new String(curToChar);if(check.equals(endWord)){return level+1;}if(wordList.contains(check)){wordQue.offer(check);nextCount++;wordList.remove(check);}}}if(curCount == 0){level++;curCount = nextCount;nextCount = 0;}}return 0;}
}