word ladder(C++ code)

LeetCode Word Ladder, Feb 11
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.

思路：bfs,我用map来记录每个单词的depth的，大集合用了1932ms...其实不需要用map，可以用两个int记录当前层和下一层的节点数，当前层用完后，当前层移到下一层，下一层则重设为0，同时update depth。这样稍微快一点，1.4s左右。。

0. int ladderLength(string start, string end, unordered_set<string> &dict) {    
1.     
2.         if(start == end) return 1;    
3.         //prev counts words of current level, next counts for next level, depth denotes current level.  
4.         //same level means same distance from original word.  
5.         int depth = 1, prev =1, next = 0;     
6.         //queue stores intermediate words  
7.         queue<string> q;    
8.      
9.         q.push(start);    
10.         //set stores visited words to avoid redundant work.  
11.         unordered_set<string> visited;    
12.     
13.         visited.insert(start);    
14.     
15.   while(!q.empty()) {    
16.     
17.     string cur = q.front();    
18.     
19.     q.pop(); prev--;    
20.     //for each letter in the intermediate word, iterate over 26 options and push it into queue if it's a word,   
21.     //don't forget to update level count next.   
22.     for(int i = 0; i < cur.length(); i++){    
23.     
24.        for(int j = 0; j < 26; j++){    
25.     
26.          string mid = cur;    
27.     
28.          mid[i] = 'a' + j;    
29.     
30.          if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){    
31.     
32.            visited.insert(mid);    
33.     
34.            q.push(mid);    
35.     
36.            next += 1;    
37.     
38.            if(mid == end) return depth + 1;    
39.          }    
40.        }     
41.    }    
42.     
43.   if(prev == 0) {prev = next; next = 0; depth++;}    
44.    
45.   }    
46.         return 0;    
47. }    

-------------用map的---------------

int ladderLength(string start, string end, unordered_set<string> &dict) {

        if(start == end) return 1;
        map<string,int> visited;

        queue<string> q;

        q.push(start);

        visited[start] = 1;

      

while(!q.empty()) {

    string cur = q.front();

    q.pop();

   for(int i = 0; i < cur.length(); i++){

       for(int j = 0; j < 26; j++){

         string mid = cur;

         mid[i] = 'a' + j;

         if(mid == end) return visited[cur] + 1;

         if(dict.find(mid) != dict.end() && visited.find(mid) == visited.end()){

           visited[mid] = visited[cur] + 1;

           q.push(mid);

     

         }

       }

   }
}

        return 0;
    }