leetcode_wordladder

leetcode_wordladder

題目描述

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,

Given:

start = “hit”

end = “cog”

dict = [“hot”,”dot”,”dog”,”lot”,”log”]

As one shortest transformation is “hit” -“hot” -“dot” -“dog” -“cog”,
return its length 5.

解題分析

此題總體思路是廣度優先BFS搜索，利用隊列可進行，但是幾次嘗試都超時：

首先我利用關系矩陣表示圖關系，這樣TLE，分析也可看到N*N的復雜度。 後來利用鄰接表方式表示，注意到這裡小寫字母只有26個，又題目說明字符串長度相同，則邊的數目最大L*26，鄰接表遍歷搜索就很快N*L*26，但是建立鄰接表的過程還是N*N，依然TLE，嘗試發現對於大數據鄰接表建立的過程中就超時了。 最後依然是利用邊數目有限的思想，由一個單詞直接去生成可達單詞然後判斷是否在字典中，這樣就不需要生成鄰接表了，這裡我由於最初數據處理使用了Linkedlist，使得在判斷是否屬於候選集的時候也就是contain object的時候費時，TLE，最後使用set結構，終於ac。 回顧很多知識點，BFS和隊列，矩陣和鄰接表，java的 set 和 collection， java的queue接口一般由linkedlist實現

詳細代碼

public class Solution {
public int ladderLength(String beginWord, String endWord, Set wordDict) {

     wordDict.add(endWord);
     wordDict.add(endWord);

     Queue queue = new LinkedList();
     queue.add(new NodeString(beginWord, 1));
     wordDict.remove(beginWord);

     while(!queue.isEmpty())
     {
          NodeString current = queue.poll();
          if(current.string.equals(endWord))
          {
              return current.deep;
          }
          else 
          {
            String tmp = current.string;//取點 找臨街的表，這裡借助最大固定數目的變數來計算而非常規利用矩陣

            for(int i=0;i