1
$\begingroup$

I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from the previous word. All permutations. Here is example:

For the set "a, b, at, bat, cat, bait". The possibilities are:

a -> at -> bat -> bait
a -> at -> cat
b

Here is my Javascript code to get all of these combinations:

function getLists(words) {

    const wordsByLength = {};
    for (const word of words) {
        const length = word.length;
        if (!wordsByLength.hasOwnProperty(length)) {
            wordsByLength[length] = [];
        }
        wordsByLength[length].push(word);
    }

    const lists = [];

    getListsUtil([], wordsByLength, lists);

    return lists;
}

function getListsUtil(list, wordsByLength, lists) {

    const lastWord = list[list.length - 1] || '';
    const oneOffWords = getOneOffWords(lastWord, wordsByLength);

    if (!oneOffWords.length) {
        lists.push(list);
        return;
    }

    for (const oneOffWord of oneOffWords) {
        getLongestListUtil([...list, oneOffWord], wordsByLength, lists);
    }


}

function getOneOffWords(targetWord, wordsByLength) {

    const oneOffWords = [];

    const targetWordLength = targetWord.length;
    const possibleWords = wordsByLength[targetWordLength + 1] || [];


    for (const possibleWord of possibleWords) {
        if (isWordOneOff(targetWord, possibleWord)) {
            oneOffWords.push(possibleWord);
        }
    }

    return oneOffWords;
}

function isWordOneOff(targetWord, possibleWord) {
    let isOneOff = false;
    let i = 0;
    let j = 0;

    while (i < targetWord.length && j < possibleWord.length) {
        if (targetWord[i] != possibleWord[j]) {
            if (isOneOff) {
                return false;
            }
            isOneOff = true;
            j++;
        } else {
            i++;
            j++;
        }
    }

    return true;
}

console.log(getLists(['a', 'b', 'at', 'cat', 'bat', 'bait']));

We can draw the call stack for this, it looks like this:

enter image description here

If we have repeating words we can get a call stack that looks like this:

a, a, a, ab, ab, ab, abc, abc, abc:

enter image description here

If we had this set of words:

a, b, c, ab, bb, cb, aba, abb, abc, bba, bbb, bbc, cba, cbb, cbc

I started drawing this callstack but I didn't finish it, we see a bunch of overlapping subproblems:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.