//

// Solution127.cpp

// Algorithm

//

// Created by Pancf on 2020/12/19.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution127.hpp"

#include <unordered_set>

int Solution127::ladderLength(std::string beginWord, std::string endWord, std::vector<std::string> &wordList)

{

// BFS

std::unordered_set<std::string> wordSet(wordList.begin(), wordList.end());

std::unordered_set<std::string> head, tail, *headPtr, *tailPtr;

if (wordSet.find(endWord) == wordSet.end()) return 0;

head.insert(beginWord);

tail.insert(endWord);

int res = 2;

while (!head.empty() && !tail.empty()) {

// ensure we always traversing smaller set

if (head.size() < tail.size()) {

headPtr = &head;

tailPtr = &tail;

} else {

headPtr = &tail;

tailPtr = &head;

}

std::unordered_set<std::string> temp;

for (auto it = headPtr->begin(); it != headPtr->end(); ++it) { // all neighbors

auto word = *it;

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

auto ch = word[i];

for (int k = 0; k < 26; k++) { // change one char each iter and find whether can transform

word[i] = 'a' + k;

if (tailPtr->find(word) != tailPtr->end()) {

return res;

}

if (wordSet.find(word) != wordSet.end()) { // if can transform, this word is the neighbor

temp.insert(word);

wordSet.erase(word);

}

}

word[i] = ch;

}

}

res++;

headPtr->swap(temp);

}

return 0;

}