-1

Preface: This implementation was source from the following video: https://www.youtube.com/watch?v=oBt53YbR9Kk

The question is regarding the space complexity of the following function:

target: string wordBank: array of strings

sample call: allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl']))

Code Implementation

const allConstruct = (target, wordBank) => {
  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const suffix = target.slice(word.length);
      const suffixWays = allConstruct(suffix, wordBank);
      const targetWays = suffix.map(way => [ word, ...way ]);
      result.push(...targetWays);
    }
  }
}

According to the video, space complexity is

O(M) | M = target.length

This makes sense, because assuming worst case where the string requires M characters to construct the target string, it will have M stack frames

However, why are we not considering the additional space generated by

const suffix = target.slice(word.length);

Where in each recursive call, we are storing potentially a M length string in memory and

const targetWays = suffix.map(way => [ word, ...way ]);

Where in each recursive call, we are storing an array of arrays whose size is also not consider within the O(m) space complexity

Is it because, we just simplify this entirety as the size of the stack frame and we say that it is

O(m) | m = number of stack frames per recursion call

If the above is the case, then why is it in the video's previous example, countConstruct:

const countConstruct = (target, wordBank) => {
  if (target === '') return 1;
  let totalCount = 0;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const numWaysForRest = countConstruct(target.slice(word.length), wordBank);
      totalCount += numWaysForRest;
    }
  }
  return totalCount;
}

Why is this example considered: O(M * M)

O(M * M) | M = number of stack frames generated, M = size of suffix stored with each call (target.slice(word.length))

jorm7012
  • 1
  • 2

2 Answers2

0

I'm attaching two other related questions asked that might help you see clearer here.

Space complexity of recursive function

How do you find the space complexity of recursive functions such as this one?

The way to see if here is as a 'tree' as mentioned in the video you've attached. What you should be looking at here essentially is how many times the function would be calling itself ( how deep it would go )

      const suffixWays = allConstruct(suffix, wordBank);

Worst case scenario as you said would be that each word is basically a letter of target. Meaning we would go through that target.indexOf(word) === 0) condition target.length time ( our M )

This gives us the 'depth' of that tree, and therefor our space complexity.

I am not sure if this really answers the question or if it helps you visualise, feel free to ask more in case, or check the two other posts I've put

Ziyed
  • 491
  • 2
  • 12
-1

With help from my friend, we concluded that the YouTube video was just inconsistent.

If we were to frame the variables differently where

m = the number of stack frames
n = the number of characters in substring

then for allConstruct() and countConstruct() space complexity is

O(c * m)

c: target.slice(word.length)
m: number of stack frames
Dharman
  • 30,962
  • 25
  • 85
  • 135
jorm7012
  • 1
  • 2