const getTransformationsByIndex = (word, index, wordList, seenSet) => {
    const leftWordPart = word.slice(0, index);
    const rightWordPart = word.slice(index + 1, word.length);

    const needle = leftWordPart + rightWordPart;

    return wordList
        .filter(selectedWord => !seenSet.has(selectedWord))
        .filter(selectedWord => {
        const haystack = selectedWord.slice(0, index) + selectedWord.slice(index + 1, word.length);
        return needle === haystack;
    })
}

const getAllTransformations =  (word, wordList, seenSet) => {
    const transformations = [];
    for (let i = 0; i < word.length; i++) {
        const transformationsByIndex = getTransformationsByIndex(word, i, wordList, seenSet);
        transformations.push(...transformationsByIndex);
    }

    return transformations;
}


const ladderLength = (beginWord, endWord, wordList) => {
    const seenBeginSet = new Set();
    const seenEndSet = new Set();

    const endWordList = [...wordList, beginWord];

    const endWordIndex = endWordList.findIndex(word => word === endWord) ;
    endWordList.splice(endWordIndex, 1);

    let beginTransformationsCount = 0;
    let endTransformationsCount = 0;

    const beginQueue = [beginWord];
    const endQueue = [endWord];

    while (beginQueue.length && endQueue.length) {
        const beginQueueLen = beginQueue.length;
        for (let i=0; i < beginQueueLen; i++) {
            const selectedBeginWord = beginQueue.shift();
            if (seenEndSet.has(selectedBeginWord)) {
               return beginTransformationsCount + endTransformationsCount;
            }

            seenBeginSet.add(selectedBeginWord);
            const beginTransformations = getAllTransformations(
                selectedBeginWord,
                wordList,
                seenBeginSet
            );

            beginQueue.push(...beginTransformations);
        }

        beginTransformationsCount++;

        const endQueueLen = endQueue.length;
        for (let i = 0; i < endQueueLen; i++) {
            const selectedEndWord = endQueue.shift();
            if (seenBeginSet.has(selectedEndWord)) {
                return beginTransformationsCount + endTransformationsCount;
            }
            seenEndSet.add(selectedEndWord);

            const endTransformations = getAllTransformations(
                selectedEndWord,
                endWordList,
                seenEndSet
            );

            endQueue.push(...endTransformations);
        }

        endTransformationsCount++;
    }

    return 0;
};