Word Ladder

/*
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.

*/
//cannot pass large tests due to execution time
class Solution {
public:
    bool isLadder(string first, string second){
      int firstSz = first.length();
      int secondSz = second.length();
     
      if(firstSz != secondSz || firstSz == 0) return false;
     
      int i;
      int distance = 0;
      for(i=0; i<firstSz; i++){
        if(first[i]!=second[i]) {
          distance++;
          if(distance > 1) return false;
        }   
      }
     
      if (distance == 1) return true;
      else return false;
    }
   
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int startSize = start.length();
        int endSize = end.length();
        if(startSize != endSize || startSize == 0) return 0;
       
        unordered_set<string>::iterator find;
        find = dict.find(start);
        if(find==dict.end()) return 0;
        find = dict.find(end);
        if(find==dict.end()) return 0;
       
        if(start.compare(end) == 0) return 1;
        if(isLadder(start, end)) return 2;
       
        int dictSize = dict.size();
        if(dictSize == 0) return 0;
       
        int firstIndex;
        int secondIndex;
        //Get dictionary into vector
        vector<string> words;
        int i = 0;
        for(unordered_set<string>::iterator it=dict.begin(); it!=dict.end(); it++){
          words.push_back(*it);
          if((*it).compare(start) == 0) firstIndex = i;
          if((*it).compare(end) == 0) secondIndex = i;
          i++;
        }
       
        int j;
        int maxSize = dictSize;
        vector<vector<int>> matrix;
        vector<int> line;
       
        //initialize matrix;
        for(i=0; i<dictSize; i++){
          line.push_back(maxSize);
        }
        for(i=0; i<dictSize; i++){
          matrix.push_back(line);
        }
       
        //build distance matrix
        for(i=0; i<dictSize; i++){
          for(j=i; j<dictSize; j++){
            if(i == j) matrix[i][i] = 0;
            else if(isLadder(words[i], words[j])){
              matrix[i][j] = 1;
              matrix[j][i] = 1;
            }
          }
        }
       
        int step = 1;
        int k;
        while(step <= dictSize-2){
          for(i=0; i<dictSize; i++){
            for(j=0; j<dictSize; j++){
               if(matrix[i][j]==step){
                 for(k=j+1; k<dictSize; k++){
                   if(matrix[i][k]==1 && matrix[j][k] == maxSize){
                      matrix[j][k] = step+1;
                      matrix[k][j] = step+1;
                   }
                 }
               }
            }                       
          }
          step++;
        }
       
        int result = matrix[firstIndex][secondIndex];
        if(result==maxSize) return 0;
        else return result+1;
    }
};