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;
    }
};

Longest Consecutive Sequence

/*

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
*/
//limitation on max size and offset
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size == 0) return 0;
        if(size == 1) return 1;
        vector<bool> indicator;
       
        int offset = 2000;
        int maxSize = 20000;
       
        int i;
        for(i=0; i<maxSize; i++){
          indicator.push_back(false);
        }
       
        for(i=0; i<size; i++){
          if((num[i]+offset) >= maxSize || (num[i]+offset) < 0) return -1;
          indicator[num[i]+offset] = true;
        }
       
        int pos = 0;
        int result = 1;
        int tempResult = 0;
       
        while(pos < maxSize){
          if((pos == 0 && indicator[pos] == true)
             ||(pos > 1 && indicator[pos-1] == false && indicator[pos] == true)){
             tempResult = 1;
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == false){
             result = max(result, tempResult);
          }
          else if(pos > 1 && indicator[pos-1] == true && indicator[pos] == true){
             tempResult++;
          }
          pos++;
        }
       
        if(indicator[maxSize-1] == true) result = max(result, tempResult);
       
        return result;
    }
};


/*
set and hash-table
*/
class Solution {

public:

int longestConsecutive(vector<int> &num)



{
  set<int> seen; // A set keeping track of whether a number is seen or not

map<int, int> startChain; // A map from the starting number to the chain size

map<int, int> endChain; // A map from the ending number to the chain size

for (int i = 0; i < num.size(); i++)



{
  int value = num[i];

if (seen.find(value) == seen.end())



{

seen.insert(value);
  map<int, int>::iterator peekStart = startChain.find(value + 1);

map<int, int>::iterator peekEnd = endChain.find(value - 1);




  // Attachable to the start and attachable to the end

if (peekStart != startChain.end() && peekEnd != endChain.end())



{
  int newStart = peekEnd->first - peekEnd->second + 1;

int newLength = peekEnd->second + 1 + peekStart->second;

int newEnd = newStart + newLength - 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);

startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the start only

if (peekStart != startChain.end() && peekEnd == endChain.end())



{
  int newStart = peekStart->first - 1;

int newLength = peekStart->second + 1;

int newEnd = newStart + newLength - 1;



startChain.erase(peekStart);

endChain.erase(endChain.find(newEnd));
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Attachable to the end only

if (peekStart == startChain.end() && peekEnd != endChain.end())



{
  int newEnd = peekEnd->first + 1;

int newLength = peekEnd->second + 1;

int newStart = newEnd - newLength + 1;



startChain.erase(startChain.find(newStart));

endChain.erase(peekEnd);
  startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}
  // Nothing else could be done - create a chain by itself

if (peekStart == startChain.end() && peekEnd == endChain.end())



{
  int newStart = value;

int newEnd = value;

int newLength = 1;

startChain.insert(pair<int, int>(newStart, newLength));

endChain.insert(pair<int, int>(newEnd, newLength));



}

}

}
  int max = 0;

for (map<int, int>::iterator startIterator = startChain.begin(); startIterator != startChain.end(); startIterator++)



{
  int current = startIterator->second;

if (current > max)



{

max = current;

}

}
  return max;



}

};