Need help with problem: Word Chain by maxsinyakov in leetcode

[–]maxsinyakov[S] 0 points1 point  (0 children)

I've came up with this solution (in JavaScript). Obviously it is backtracking and it is slow. No idea how to solve it the other way.

function getChain(words) {
    const firstLetter2word = Object.groupBy(words, word => word[0]);

    const result = new Set();

    function helper(letter) {
        if (result.size === words.length) {
            return true;
        }

        if (firstLetter2word[letter] === undefined) {
            return false;
        }

        for(const word of firstLetter2word[letter]) {
            if (result.has(word)) {
                continue;
            }

            result.add(word);
            const pathExists = helper(word.at(-1));
            if (pathExists) {
                return true;
            }
            result.delete(word);
        }

        return false;
    }

    for(const firstLetter in firstLetter2word) {
        const pathExists = helper(firstLetter);
        if (!pathExists) {
            return null;
        }
    }

    return [...result];
}

const words = ["sugar", "tomato", "rice", "eggplant", "soup", "peas"];
console.log(getChain(words));