[leetcode] Word Ladder I

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.

Basic Stuff:

This is a good question that I learnt a lot.

1. The unordered_set<xxx> is a good data structure that hold dictionary. It is similar as hashtable but not exactly the same. Insert(), find(), remove() can be done in constant time. 

2. If you can do bi-directional search, Bi-BFS is a great way to use for this problem.

Algorithm:

1. The basic idea for this problem is to build  a tree structure. Start from the start string, find the qualified next strings in the dictionary and then do the same thing on those strings. 

2. We can do a BFS on the tree as we need the shortest path. 

3. As we can also search from the end, we could use the Bi-directional BFS to get that while they meet at some point. This would make the search time to n/2

4. The truth is that when we find the meeting point, it should both on the lowest level of the start tree and also the lowest level of the end tree. 

5. The right level should be the be-found tree's front() + opposite direction tree's end().

My Code:

bool valid(string start, string end){                             
        if(start.length() != end.length()) return false;          
        int count = 0;
        for(int i = 0; i < start.length(); ++i){                  
            if(start[i]!=end[i]){                                 
                count++;
                if(count > 1) return false;
            }
        }
        return true;
}

vector FindinDict(string source, unordered_set &dict){ 
   vector ret;
   if(source.empty() || dict.empty()) return ret;
   for(int i = 0; i < source.length(); i++){
       string curs = source;
       for(char j = 'a'; j <='z'; j++){
           curs[i] = j;
           auto fd = dict.find(curs);
           if(fd != dict.end()){
               ret.push_back(*fd);
           }
       }
   }
   return ret;
}

struct node{
   string str;
   int lev;
   node(string s, int l){str = s; lev = l;}
};

int ladderLength(string start, string end, unordered_set &dict) {
   if(valid(start, end)) return 2;
   queue sq;
   queue eq;
   map svisited;
   map evisited;

// Should initialize the maps.
   for(auto it = dict.begin(); it != dict.end(); ++it){
        svisited[*it] = false;
        evisited[*it] = false;
   }
  sq.push(node(start,1));
  eq.push(node(end,1));
  svisited[start] = true;
  evisited[end] = true;
  int slevel = 1;
  int elevel = 1;

// Here use the queue size to control the expand of each tree. But still expand 

// level by level
  while(!sq.empty() && !eq.empty()){
    if(sq.size() < eq.size()){
        while(!sq.empty() && sq.front().lev == slevel){
            vector snxt = FindinDict(sq.front().str, dict);
            for(auto it = snxt.begin(); it != snxt.end(); ++it){
                if(!svisited[*it]) {
                    sq.push(node(*it, slevel+1));

                    // When to set the visited true is crucial in BFS.
                    svisited[*it] = true;
                }
                if(evisited[*it]) return (sq.front().lev+eq.back().lev);
            }
            sq.pop();
        }
        slevel++;
     }
    else{
        while(!eq.empty() && eq.front().lev == elevel){
            vector enxt = FindinDict(eq.front().str, dict);
            for(auto it = enxt.begin(); it != enxt.end(); ++it){
                if(!evisited[*it]) {
                    eq.push(node(*it, elevel+1));
                    evisited[*it] = true;
                }
                if(svisited[*it]) return (eq.front().lev + sq.back().lev);
            }
            eq.pop();
        }
      elevel++;
    }
  }
  return 0;
}