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

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] = [];

    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) {

    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)) {

    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;
        } else {

    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


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.