Word Ladder

//passed small test, but not big test yet

class Solution {
    unordered_set<string> dict;//short dictionary
    bool off_by_one(string const& s1, string const& s2){
      int counter = 0;
      for(unsigned int ii = 0; ii < s1.length(); ++ii){
        if (s1[ii] != s2[ii]) ++counter;
        if (counter >= 2) return false;
      }
      return (1 == counter);
    }
    
    class Node{
        public:
          Node(string name):word(name),parent(0){}
          string word;
          vector<Node*> children;
          Node* parent;
    };
    
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int const word_length = start.length();
        for(auto word:dict){
            if (word.length() == word_length)
            this->dict.insert(word);
        }
        return mutationPath(start,end).size();
    }
    
    vector<string> mutationPath(string const& source, string const& dest){
    
      vector<string> result;
      Node* sp = new Node(source);
      if (source!=dest)dict.erase(source);
      deque<Node*> frontier;
      frontier.push_back(sp);
      while(!frontier.empty()){
        Node* node = frontier.front(); frontier.pop_front();
        string const word = node->word;
        for (auto it = dict.begin(); it != dict.end();){
          string const neighbor(*it);
          if (off_by_one(word, neighbor)){
            if (dest == neighbor){
              result.push_back(neighbor);
              while(node){
                result.push_back(node->word);
                node = node->parent;
              }
              return vector<string>(result.rbegin(),result.rend());
            }
            dict.erase(it++);
            auto it_n = new Node(neighbor);
            node->children.push_back(it_n);
            node->children.back()->parent = node;
            frontier.push_back(it_n);
          }else ++it;
        }//for it
      }//while not empty
      return result;
      //--------------------------
    }
};

//Another way, but still does not pass the big test

class Solution {
    struct Node{
        string name;
        int count;
        Node(string n, int cnt = 0):name(n),count(cnt){}
    };
    string const alphabet{"abcdefghijklmnopqrstuvwxyz"};
    vector<string> neighborList(string const& word){
        vector<string> neighbors;
        for(int ii = 0; ii < word.length(); ++ii){
            int const firstLength = ii;
            int const secondLength = word.length() - firstLength - 1;
            string firstPart = word.substr(0,firstLength);
            string secondPart = word.substr(ii+1, secondLength);
            for(char c:alphabet){
                if (c != word[ii]) neighbors.push_back(firstPart+c+secondPart);
            }
        }
        return neighbors;
    }
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        set<string> sdict;//short dict
        int const word_length = start.length();
        for(auto word: dict){
            if (word.length() != word_length) continue;
            sdict.insert(word);
        }
        deque<Node> frontier{Node(start)};
        while(!frontier.empty()){
            Node currentNode = frontier.front();
            frontier.pop_front();
            vector<string> neighbors = neighborList(currentNode.name);
            for(string neighbor_candidate: neighbors){
                set<string>::iterator it = sdict.find(neighbor_candidate);
                if (it != sdict.end()){
                    if (end == neighbor_candidate) return currentNode.count+2;
                    frontier.push_back(Node(neighbor_candidate, currentNode.count+1));
                    sdict.erase(it);
                }
            }
        }
        return 0;
    }
};