Letter Combinations of a Phone Number - Backtracking - Leetcode 17

0:00 - Read the problem
2:30 - Drawing Explanation
6:10 - Coding Solution

leetcode 17

#phone #combination #python

[themagickalmagickman]

I'd suggest putting this as the first problem in your backtracking list on neetcode list as its the most straightforward I think

[PAIPENG-cb]

for those who might get confused by pop(), here the size of the return list are always the same, so it doesnt need to pop the element to give space for the next one. It just need to straight forwardly add all the possible subsets to the result

[baap]

best coding channel for DSA and best approaches.
Love From India❤

[ThethProgrammer]

The time complexity would be worse than O(N*4^N) because you are passing curStr by value which means for each call to backtrack() you are performing a string copy. If you passed currStr by reference then N*4^N would be correct (but then you would need to also remove elements from the end of the string when backtrack() returned using pop). And for anyone still confused about the N in the time complexity given, at each of the solutions (of which there are at most 4^N), we are copying a string of length N to the result which is a linear time operation. So O(4^N * N).

[jiwachhetri]

His explanation makes it so easy to understand even for beginners

[jay-rathod-]

NeetCode your channel is going to be at the top someday. Good explaination and good code....

But one request:

Whenever you get time. Just partition this playlist into either Data structure or algorithmic approach paradigm. Instead of just naming it Coding interview solutions.

[sjl]

For those who wondered why there's no append or pop (similar to the other backtracking approaches) it's because strings are immutable. Everytime the call is made to the backtrack method, python creates a new string so when the method returns up the stack, the caller still has the original string without the concatenated letter.

[jamestruong]

Hi Neet, loved the solution- it was very concise and simple.
One thing I would add to the explanation is that you made it seem like it was a breadth first solution instead of a depth first solution inside your diagram segment.
The for-loop executes after each backtracking return, not when they are called. In other words, the next iteration of the for loop is only executed after the first completed string.

[oofy]

Similar idea and coding as #78 Subset but more easier. Thanks so much for the explanations!

[zehuazhou]

Have you considered doing an iterative solution? I think it is doable. Take the "23" input for example, we can init our index array to be [0, 0]. Then we would output "ad" first, because the first 0 maps to a in [a, b, c] array, and the second 0 maps to d in [d, e, f] array. Then we can add 1 to 00, which becomes 01, and this gives us ae. Then add 1 again, and it becomes 02 and we get af. Then add 1 again and then it overflows because [d, e, f] does not have index 3 in it, so we reset this to 0 and increment the first 0 to 1, and it changes from 02 to 10. We complete the loop when the first digit overflows.

[Chansd]

This is not on your Neetcode 150 nor Blind 75, but I was practicing this as a variation of "Generate Parentheses" and I'm delighted you have a solutions video! Amazing content for normal, non geniuses like me who struggle through these problems! You sir, are a live saver!

[jkk-gc]

I somehow coded the solution myself, but wasn't sure why it worked. You have the best explanations

[theraczcar]

This helped me with getting through a coding problem to find out possible pins from a keypad! Thanks a ton this makes recursion a little less scary!

[rajeshmadira]

Excellent explanation, Please try to explain more problems per week

[IsomerMashups]

I've learned not to trust leetcode's runtime number because I ran the same algorithm twice and the first time it put me in the bottom 5% and the second it put me in the top 25%.

[Thisismyworld]

Hey.. great solution to solve this problem but it doesn't use the concept of backtracking. You are currently parsing the whole recursion tree without pruning it. Pls update!

[jsdev]

actually I'm curious, would this solution be considered as "backtracking" ? as we aren't returning the value once the base case is hit, but rather building each solution as we get further into the recursion calls. Obviously nothing major, just trying to solidify my concepts. I realize some recursion solutions are built as we get deeper into the call, and other solutions are returned one by one after hitting the base case.

[umberto]

why is the time complexity O(n * 4^n) and not just 4^n, where we have 4 choices at a height of n

[albertlee]

I think it's more efficient to append a letter to a list and join at the end of the recursions than to add strings since string is immutable

[AnnieBox]

backtracking is always my painpoint but everything looks so neat and easy to understand from you video!👍🏻