CODEWITHSUNDEEP
dynamic-programming
Dorian McAllister
Dorian McAllister

Reputation: 785

Dynamic Programming Question - What is the base case?

Been preparing of Coding Interviews. I have been trying to beef up my dynamic programming skills and came across Alvin's awesome channel and this great video about some of the approaches to take. In one of the programming sections - The problem statement is "Can you construct the target string with the contents in an array" - he goes on to correctly use recursion as an approach. But I got stuck in his base case.

He indicates for example that this should return true:

canConstruct('StakeBoard', ['sta', 'te', 'bo', 'ard']

He goes on to settle the recursion base case as the following returning true by literally saying "Because to generate and empty string, you can generally take no-zero elements from the array!". This is the part I did not understand. What does non-zero elements of the array mean here to make this a base case?

canConstruct('', ['cat', dog'])

Upvotes: 1

Views: 439

Answers (1)

tanmoy
tanmoy

Reputation: 1438

"Because to generate an empty string, you can generally take no-zero elements from the array!"

It should be something like

"Because to generate an empty string, you can generally take no or zero elements from the array!"

The next question states that

What does non-zero elements of the array mean here to make this a base case?

Actually, he meant

In case the target is empty, no matter what array of words are given, taking no or zero words will return the answer true.

We call a case base case when we have a definite answer for that case. And the case described above definitely looks like one thereby addressed as the base case.

Upvotes: 1

Related Questions