原題鏈接在這里: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;} }
跟上Word Ladder II.
Reference:?http://www.cnblogs.com/springfor/p/3893499.html