leetcode-WordLadder

Word Ladder

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

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

   Note:
   

   • Return 0 if there is no such transformation sequence.
   • All words have the same length.
   • All words contain only lowercase alphabetic characters.
     
     此題是圖的遍歷問題，要找一條起始點到目標點最短的路徑，如果存在這樣的路徑則返回路徑長度，否則返回0。 剛開始想到用深度優先搜索遍歷，但是時間復雜度太大，於是轉為用寬搜，把起始點放入隊列中，隊列中的節點是一個字符串，因為要找到最短路徑，所以在取出隊首節點時要知道該節點屬於第幾層被搜索的節點，即路徑長度，我用了levels來保存當前遍歷的是第幾層的節點，然後擴展該節點，把編輯距離為1並且在字典中出現的字符串加入隊尾，並從字典中刪除該字符串。
     

     在找編輯距離為1的字符串時，我試了兩種方法，一種是遍歷字典，找到編輯記錄為1的字符串，如果字典數目很大的話，每次都遍歷字典耗時太多了，結果就是TLE，後來直接對節點字符串進行修改一個字符來得到擴展字符串才通過。

     class Solution {
     public:
         typedef queue> qq;
         int ladderLength(string start, string end, unordered_set &dict) {
             //Use queue to implement bfs operation
             qq q;
             q.push(start);
             dict.erase(start);
             
             int currLevelLens = 1, nextLevelLens; 
             int levels = 1;  //To be returned answer, the total bfs levels be traversed
             string front, str;
             
             while (!q.empty()) {
                 nextLevelLens = 0;
                 while (currLevelLens--) {  // Traverse the node of current level
                     string front = q.front();
                     q.pop();
                     if (front == end)
                         return levels;
                     for (int i=0; i
     
     
     
     
     
     但是這樣的方法改變了dict的內容，有沒有不改變dict的方法呢？我試了用一個unorder_set來保存被搜索過的字符串,但是耗時比前一種方法多。
     
     
     class Solution {
     public:
         typedef queue> qq;
         int ladderLength(string start, string end, unordered_set &dict) {
             //Use queue to implement bfs operation
             qq q;
             q.push(start);
             
             int currLevelLens = 1, nextLevelLens; 
             int levels = 1;  //To be returned answer, the total bfs levels be traversed
             string front, str;
             searchedStrs.insert(start);
             while (!q.empty()) {
                 nextLevelLens = 0;
                 while (currLevelLens--) {  // Traverse the node of current level
                     string front = q.front();
                     q.pop();
                     if (front == end)
                         return levels;
                     for (int i=0; i searchedStrs;
     };
     
     
     
     
     
     
     
     Python解法：
     
     有參考Google Norvig的拼寫糾正例子：http://norvig.com/spell-correct.html
     
     
     class Solution:
         # @param word, a string
         # @return a list of transformed words
         def edit(self, word):
             alphabet = string.ascii_lowercase
             splits = [(word[:i],word[i:]) for i in range(len(word)+1)]
             replaces = [a+c+b[1:] for a,b in splits for c in alphabet if b]
             replaces.remove(word)
             return replaces
             
         # @param start, a string
         # @param end, a string
         # @param dict, a set of string
         # @return an integer
         def ladderLength(self, start, end, dict):
             currQueue = []
             currQueue.append(start)
             dict.remove(start)
             ret = 0
             while 1:
                 ret += 1
                 nextQueue = []
                 while len(currQueue):
                     s = currQueue.pop(0)
                     if s == end:
                         return ret
                     editWords = self.edit(s)
     
                     for word in editWords:
                         if word in dict:
                             dict.remove(word)
                             nextQueue.append(word)
                 if len(nextQueue)==0:
                     return 0
                 currQueue = nextQueue
             return 0