[譯]字梯

原文連結: 字梯

給定兩個單詞(開始和結束)和一個字典，從開始到結束找到最短轉換序列的長度，這樣隻有一個字母可以在一個時間内改變，而每個中間字必須存在于字典中。

例如,給定:

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
           

一個最短的轉換是"hit" -> "hot" -> "dot" -> "dog" -> "cog", 程式應該傳回它的長度5。

分析

更新于2015年6月7日

是以，我們很快意識到這是一個搜尋問題，并且第一次搜尋保證了最優解。

圖1

Java解決

class WordNode{
    String word;
    int numSteps;
 
    public WordNode(String word, int numSteps){
        this.word = word;
        this.numSteps = numSteps;
    }
}
 
public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        LinkedList<WordNode> queue = new LinkedList<WordNode>();
        queue.add(new WordNode(beginWord, 1));
 
        wordDict.add(endWord);
 
        while(!queue.isEmpty()){
            WordNode top = queue.remove();
            String word = top.word;
 
            if(word.equals(endWord)){
                return top.numSteps;
            }
 
            char[] arr = word.toCharArray();
            for(int i=0; i<arr.length; i++){
                for(char c='a'; c<='z'; c++){
                    char temp = arr[i];
                    if(arr[i]!=c){
                        arr[i]=c;
                    }
 
                    String newWord = new String(arr);
                    if(wordDict.contains(newWord)){
                        queue.add(new WordNode(newWord, top.numSteps+1));
                        wordDict.remove(newWord);
                    }
 
                    arr[i]=temp;
                }
            }
        }
 
        return 0;
    }
}