Definitely agree, I trained so much with the previous backtracking problems that when I got to this one I solved it within 6 minutes and was like: wait, that's all? (btw for the sake of comparison some of the previous problems took me like 30+ minutes to solve)
@@fredtrentini6791 totally agree. I thought I had done something wrong when I solved with this one as it was so much easier I thought I was missing something.
nah I feel like you definitely need to know whats up to be able to solve this. I was able to (not to toot my own horn) but I felt significantly more proud of solving this than i did for like combination sum ii or something
Unfortunately he's not taking our wishes into account. It's still in the end. And Generate Parenthesis from Stack section should be in Backtracking too.
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.
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.
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
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).
This is not true for python. There is no separate pass by value & pass by reference in python as in C++. It's only pass by reference (to be pedantic, a reference is passed by value - same in java). The issue here is string concatenation.
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.
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.
I just had a try with the above iterative plan and the running time and memory usage are better: Runtime: 1 ms, faster than 76.76% of Java online submissions for Letter Combinations of a Phone Number. Memory Usage: 37.9 MB, less than 75.15% of Java online submissions for Letter Combinations of a Phone Number.
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!
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%.
yeah, there's actually a meme about having the phone tech interviews at a certain time if they straight up use leetcode because less server latency hit lmao.
I mean even if there is no dedicated backtracking funciton call, isn't it technically still backtracing because we are appending a new character to 'curStr' in the function call itself and everytime that funciton is popped from the recursion stack, the character that we last appended gets removed automatically and hence we essentially just backtracked.
I think there is a lot of confusion around what backtracking is. Just because you explore the entire set of possibilities and all of them are valid does not mean an approach does not use backtracking. "Pruning" can make backtracking algorithms more efficient by eliminating invalid solutions as they are encountered but is not required for backtracking. From Geeks for Geeks: "Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end." The dead end in this case is simply the length of the candidate strings we are building.
It can be, if you use a list of characters and ‘’.join(characters) in the base case - instead of passing strings. Doing so is more time and memory efficient
In backtracking problems like **_Letter Combinations of a Phone Number_**, you can use two common approaches for building strings: --- #DIFF BW with pop and without pop ### **1. Using `pop()` (String Builder with List):** - **How it works**: You use a **list** as a mutable string builder. `append()` adds characters, and `pop()` removes them during backtracking. - **Efficiency**: - **Time Complexity**: `append()` and `pop()` are **O(1)**, making it faster for modifying the list. - **Memory**: Modifies the list in-place, reducing memory overhead. - **Backtracking**: After exploring one path, `pop()` removes the last letter, allowing the next possibility to be explored. ```python def backtrack(index, path): if len(path) == len(digits): combinations.append("".join(path)) return for letter in letters[digits[index]]: path.append(letter) backtrack(index + 1, path) path.pop() # Backtrack ``` --- ### **2. Not Using `pop()` (Direct String Concatenation):** - **How it works**: You pass a new **string** in each recursive call (`path + letter`), avoiding in-place modification. - **Efficiency**: - **Time Complexity**: String concatenation creates a new string each time, which is **O(n)** where `n` is the string length. - **Memory**: Each recursive call creates a new string, using more memory. - **Backtracking**: No need for `pop()` since you create a new string each time. ```python def backtrack(index, path): if len(path) == len(digits): combinations.append(path) return for letter in letters[digits[index]]: backtrack(index + 1, path + letter) ``` --- ### **Key Difference**: - **Using `pop()`**: Faster with **O(1)** list operations (_string builder_), better for performance. - **No `pop()`**: Easier to implement, but less efficient due to repeated string creation (**O(n)** for each concatenation). ---
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!
Each backtracking, seems like the solution is copying the entire string again and again. So its O(n*4^n) ? for char in digit_map[digit]: curr.append(char) recur(i+1, curr) curr.pop() this would be better like other backtracking solution. Perhaps this question was done before the other questions
At each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
At first I was confused why we didn't pop from curStr after the call to backTrack(). Can someone check my reasoning here? We don't need to pop from curStr because curStr + c implicitly creates a copy of curStr with c appended to it. Therefore, each recursive call gets a different copy of curStr so no clean up (popping) is needed. This is in contrast to problems where each recursive call gets an array passed to it. Since, in those problems, each recursive call gets the same reference to the array. Meaning that clean up is needed because you don't want values from this recursive call to be present in other calls.
Shouldn't you, for example, save in the dict patterns such as "23" in the input string "2323"? I pretty much treated this problems as a hash map problem, and got way better results.
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.
So backtracking is recursion. The reason why this solution is considered backtracking is because regardless of hitting a base case or a solution where we return earlier (i think it's called pruning) we still have to complete the tree and go through every possible combination.
Hey Neetcode, I have one question! but before that a big thanks from bottom of heart for your wonderful solutions, this helps a lot. so my question is how do you come up with such a super precise solutions, are you born intelligent or is it because of lot of practice? how?? I want to know.. even I want to come with such good solutions with out having to watch your video's. Thanks anyway:)
It's undeniable that my boy here is quite smart, but it is also true that with enough effort you can learn the patterns and start recognizing then when reading a problem. It's all practice and persistence bro!
why you classify this question as a "backtrack" question? It looks like just a regular dfs to me. For backtrack, we usually have those types of "append-pop" thing
Sorry I'm late but I'm commenting for my own understanding as well. The reason we do the append pop thing is because we're using a shared set/list which is getting passed down. So, when we go up the decision tree, we need to make sure to pop the current elements we've used. However, when we're using strings, we don't need to do that since a new String is created for each recursive call. The string in the original recursive call hasn't changed as a result of the calls.
@@PippyPappyPatterson It is still backtracking. The only difference is the manipulation. We don't need to have an append/pop thing, but the algorithm still works in a backtracking way. Backtracking is more a concept than an implementation.
def letter_combinations(digits): digit_to_letters = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' } if not digits: return [] result = [''] for digit in digits: letters = digit_to_letters.get(digit, '') result = [prefix + letter for prefix in result for letter in letters] return result # Example usage phone_number = "23" combinations = letter_combinations(phone_number) print(combinations) # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
4^n is for the worst case scenario but the length of the string that we will be returning in the list will be of length 'n', same as the input string length. Therefore the time complexity is O(n*4^n)
The complexity is O(4^n). It's a "permutation with repetition" which is r^n, where r is the number of options you have for each digit and n is the number of digits. The "worst case" means that we use 4 rather than 3, since the 7 and 9 buttons have 4 characters we assume all buttons have 4 characters.
"4^n" is every combination that is made in a decision tree (in worst case Example: "999..9") multiplied by "n'" the actual length of each output string (which is the same length as our input string n)
The simple explanation to your question is at each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
Using the digits input as a stack was a simpler solution for me, felt like cheating cus i skipped recursion lol letters = {'2': ['a','b','c'],'3': ['d','e','f'],'4': ['g','h','i'],'5': ['j','k','l'],'6': ['m','n','o'],'7': ['p','q','r','s'],'8': ['t','u','v'],'9': ['w','x','y','z']} digits = list(digits) if not digits: return [] res = letters[digits.pop()] while digits: last = letters[digits.pop()] newres = [] for i in range(len(res)): for j in range(len(last)): newres.append(last[j] + res[i]) res = newres return res
this is not backtracking??? there is no code that undos your choice so i think it is more accurate to say that it just traverses the entire graph??? i think for backtracking you would want to keep a record of used values so that you can skip them and be able to reverse your choices whereas here you do not have to since you are only going deeper into the graph
You can choose one of them. Both are valid solutions. For me uses backtrack(i+1, curStr+c) with res.append(curStr) is easier to think than build the combination from return backtrack().
We can write the function outside the first function. Why are you defining it inside another function? can anyone tell advantages and disadvantages of it?
The code builds a new string for every recursive call. On the other hand, when you pass in a list, that list is the same list for every recursive call.
We pop when our subset is an array we’re building and we want say 1,2 as one tree and 1,3 as another choice. We would need to pop the 2 from 1,2 so we can use the 1,3 combination. Then we continue with the rest of the numbers that same way. We’re using the same subset array so we have to pop to change the combination of numbers, or letters. Our combinations in this particular problem are made from letters in each property in the digitToChar object. So there’s no need to pop since the next digits’s characters contain the other choices we need to add to our string.
how can i think like this in a first place. I usually able to think only solution with iteration. how can I improve my problem solving with recursion .help please.
At each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
He does it a couple times in his solutions: an inner function that iterates over the input and populates a list: he does this with DFS problems where the side effect of DFS is appending the popped vertex to the resulting list. backtrack's main function is to iterate over all the list of chars for a number and append to the result which will be returned
if you take his example 23 backtrack will be called as below: for each of the letter of first digit, it will be called with letter of second digit. SO base case will be covered when len(digit) == len(charStr) for example 2 is equal to 'ad' i.e in inner outer loop. (inner loop 1) backtrack(1,a) (inner outer loop 2,3,4) backtrack(2,ad) backtrack(2,ae) backtrack(2,af) (inner loop 2)backtrack(1,b) (inner outer loop 2,3,4) backtrack(2,bd) backtrack(2,be) backtrack(2,bf) (inner loop 3)backtrack(1,c) (inner outer loop 2,3,4) backtrack(2,cd) backtrack(2,ce) backtrack(2,cf)
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
I'd suggest putting this as the first problem in your backtracking list on neetcode list as its the most straightforward I think
Definitely agree, I trained so much with the previous backtracking problems that when I got to this one I solved it within 6 minutes and was like: wait, that's all?
(btw for the sake of comparison some of the previous problems took me like 30+ minutes to solve)
@@fredtrentini6791 i thought i was the only one hustling this long with 30 lines of code writing.
@@fredtrentini6791 totally agree. I thought I had done something wrong when I solved with this one as it was so much easier I thought I was missing something.
nah I feel like you definitely need to know whats up to be able to solve this. I was able to (not to toot my own horn) but I felt significantly more proud of solving this than i did for like combination sum ii or something
Unfortunately he's not taking our wishes into account. It's still in the end. And Generate Parenthesis from Stack section should be in Backtracking too.
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.
that day has come 😁
sale joy. mera future dekh ke baata de @jay-rathod-youtube
@@TheModernPolymath ur mom has come [1]
[1] ruclips.net/video/qAs9laxC-rs/видео.html
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.
This was confusing me, thanks a lot!
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
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).
This is not true for python. There is no separate pass by value & pass by reference in python as in C++. It's only pass by reference (to be pedantic, a reference is passed by value - same in java). The issue here is string concatenation.
His explanation makes it so easy to understand even for beginners
best coding channel for DSA and best approaches.
Love From India❤
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.
Similar idea and coding as #78 Subset but more easier. Thanks so much for the explanations!
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.
I just had a try with the above iterative plan and the running time and memory usage are better: Runtime: 1 ms, faster than 76.76% of Java online submissions for Letter Combinations of a Phone Number.
Memory Usage: 37.9 MB, less than 75.15% of Java online submissions for Letter Combinations of a Phone Number.
@@zehuazhou3390 can you share your code? thanks
Excellent explanation, Please try to explain more problems per week
I somehow coded the solution myself, but wasn't sure why it worked. You have the best explanations
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!
Recursion's a total beast. It scares me. But I can do anything if Neetcode babysteps me little by little :)
@@Chansd5 fr fr, It demotivated me so much that i had stopped doing leetcode problems. Then, i found NeetCode *heavenly music plays*
This actually makes it more confusing to me 😢
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!
It is on neetcode 150, it's under backtracking as the 2nd last
@@torin755 Gotcha! I'm still working on "Stacks" and on my way down.
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%.
yeah, there's actually a meme about having the phone tech interviews at a certain time if they straight up use leetcode because less server latency hit lmao.
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
backtracking is always my painpoint but everything looks so neat and easy to understand from you video!👍🏻
this the only tech foreign channel I follow from India. Good going
ur mom's from india
great approach but is this backtracking!!?? i think its recursive only
Correct, still a nice approach
I mean even if there is no dedicated backtracking funciton call, isn't it technically still backtracing because we are appending a new character to 'curStr' in the function call itself and everytime that funciton is popped from the recursion stack, the character that we last appended gets removed automatically and hence we essentially just backtracked.
I think there is a lot of confusion around what backtracking is. Just because you explore the entire set of possibilities and all of them are valid does not mean an approach does not use backtracking. "Pruning" can make backtracking algorithms more efficient by eliminating invalid solutions as they are encountered but is not required for backtracking. From Geeks for Geeks: "Backtracking is a problem-solving algorithmic technique that involves finding a solution incrementally by trying different options and undoing them if they lead to a dead end." The dead end in this case is simply the length of the candidate strings we are building.
@@The6thProgrammercorrect
It can be, if you use a list of characters and ‘’.join(characters) in the base case - instead of passing strings. Doing so is more time and memory efficient
In backtracking problems like **_Letter Combinations of a Phone Number_**, you can use two common approaches for building strings:
---
#DIFF BW with pop and without pop
### **1. Using `pop()` (String Builder with List):**
- **How it works**: You use a **list** as a mutable string builder. `append()` adds characters, and `pop()` removes them during backtracking.
- **Efficiency**:
- **Time Complexity**: `append()` and `pop()` are **O(1)**, making it faster for modifying the list.
- **Memory**: Modifies the list in-place, reducing memory overhead.
- **Backtracking**: After exploring one path, `pop()` removes the last letter, allowing the next possibility to be explored.
```python
def backtrack(index, path):
if len(path) == len(digits):
combinations.append("".join(path))
return
for letter in letters[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop() # Backtrack
```
---
### **2. Not Using `pop()` (Direct String Concatenation):**
- **How it works**: You pass a new **string** in each recursive call (`path + letter`), avoiding in-place modification.
- **Efficiency**:
- **Time Complexity**: String concatenation creates a new string each time, which is **O(n)** where `n` is the string length.
- **Memory**: Each recursive call creates a new string, using more memory.
- **Backtracking**: No need for `pop()` since you create a new string each time.
```python
def backtrack(index, path):
if len(path) == len(digits):
combinations.append(path)
return
for letter in letters[digits[index]]:
backtrack(index + 1, path + letter)
```
---
### **Key Difference**:
- **Using `pop()`**: Faster with **O(1)** list operations (_string builder_), better for performance.
- **No `pop()`**: Easier to implement, but less efficient due to repeated string creation (**O(n)** for each concatenation).
---
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!
Each backtracking, seems like the solution is copying the entire string again and again. So its O(n*4^n) ?
for char in digit_map[digit]:
curr.append(char)
recur(i+1, curr)
curr.pop()
this would be better like other backtracking solution. Perhaps this question was done before the other questions
why is the time complexity O(n * 4^n) and not just 4^n, where we have 4 choices at a height of n
Yeah, I get that it's more than 4^n, but I'm not convinced that it's n * 4^n.
At each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
At first I was confused why we didn't pop from curStr after the call to backTrack(). Can someone check my reasoning here?
We don't need to pop from curStr because curStr + c implicitly creates a copy of curStr with c appended to it. Therefore, each recursive call gets a different copy of curStr so no clean up (popping) is needed. This is in contrast to problems where each recursive call gets an array passed to it. Since, in those problems, each recursive call gets the same reference to the array. Meaning that clean up is needed because you don't want values from this recursive call to be present in other calls.
correct
yea, we have to pop if using Java with StringBuilder -- curr is a reference type and pass in a reference so we need to change it back manually.
Shouldn't you, for example, save in the dict patterns such as "23" in the input string "2323"? I pretty much treated this problems as a hash map problem, and got way better results.
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.
So backtracking is recursion. The reason why this solution is considered backtracking is because regardless of hitting a base case or a solution where we return earlier (i think it's called pruning) we still have to complete the tree and go through every possible combination.
yes i was thinking the same thing this does not seem like backtracking which is kind of misleading
@@hamoodhabibi7026 I think of non-backtracking recursive solutions as DFS solutions.
Great explanation, please keep it up! :)
Hey Neetcode, I have one question! but before that a big thanks from bottom of heart for your wonderful solutions, this helps a lot. so my question is how do you come up with such a super precise solutions, are you born intelligent or is it because of lot of practice? how?? I want to know.. even I want to come with such good solutions with out having to watch your video's.
Thanks anyway:)
It's undeniable that my boy here is quite smart, but it is also true that with enough effort you can learn the patterns and start recognizing then when reading a problem. It's all practice and persistence bro!
Earlier, Backtracking was nightmare for me. Now, It is easier than any algorithm I have learned till now.
This solution beats 19%, I did this iteratively and it beat 96%.
First thing I thought about is a graph problem with an Inorder traversal
I am curious where is the backtracking part of this question 🤔
So neat, this deserves a lot more likes
I would suggest that you should have explained this with
input "234"
Amazing.... Didnt think that we can use recursion
I'm finally getting backtracking algorithms in < 20m :-.) maybe I'll actually be able to get a job, tysm Leetcode king
Great video! Can I please ask how did you make a video like this? What tools did you use? thank you!
This question is asked today to me in amazon interview :) Could not answer :D
why you classify this question as a "backtrack" question? It looks like just a regular dfs to me. For backtrack, we usually have those types of "append-pop" thing
Sorry I'm late but I'm commenting for my own understanding as well. The reason we do the append pop thing is because we're using a shared set/list which is getting passed down. So, when we go up the decision tree, we need to make sure to pop the current elements we've used. However, when we're using strings, we don't need to do that since a new String is created for each recursive call. The string in the original recursive call hasn't changed as a result of the calls.
@@atishayjain3011 So… still not backtracking kek
@@PippyPappyPatterson What do you mean? It is absolutely backtracking.
@@atishayjain3011 > we don't need to do that [backtracking] since a new String is created for each recursive call
@@PippyPappyPatterson It is still backtracking. The only difference is the manipulation. We don't need to have an append/pop thing, but the algorithm still works in a backtracking way. Backtracking is more a concept than an implementation.
Thank you for the explanation/solution!
I always forgot drawing the decision tree :(
I think "curStr + c" costs O(n), so it's actually more than O(4^n*n) unless you only join the string in the end.
I agree, I think with string concat logic, it should be O(4^n * n^2), if we use a list to store the string, then the complexity would be O(4^n*n)
wish you would go over base cases in your code. It would be helpful if you go over it in real time
def letter_combinations(digits):
digit_to_letters = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
if not digits:
return []
result = ['']
for digit in digits:
letters = digit_to_letters.get(digit, '')
result = [prefix + letter for prefix in result for letter in letters]
return result
# Example usage
phone_number = "23"
combinations = letter_combinations(phone_number)
print(combinations) # Output: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
I was asked this question at Facebook interview.
Wow
can someone please explain why the time complexity is O(n*4^n)? and not O(4^n)? Thank you.
4^n is for the worst case scenario but the length of the string that we will be returning in the list will be of length 'n', same as the input string length. Therefore the time complexity is O(n*4^n)
The complexity is O(4^n). It's a "permutation with repetition" which is r^n, where r is the number of options you have for each digit and n is the number of digits.
The "worst case" means that we use 4 rather than 3, since the 7 and 9 buttons have 4 characters we assume all buttons have 4 characters.
"4^n" is every combination that is made in a decision tree (in worst case Example: "999..9") multiplied by "n'" the actual length of each output string (which is the same length as our input string n)
@@hamoodhabibi7026 but you don't perform `n` operations for each of the `4^n` combinations
The simple explanation to your question is at each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
Using the digits input as a stack was a simpler solution for me, felt like cheating cus i skipped recursion lol
letters = {'2': ['a','b','c'],'3': ['d','e','f'],'4': ['g','h','i'],'5': ['j','k','l'],'6': ['m','n','o'],'7': ['p','q','r','s'],'8': ['t','u','v'],'9': ['w','x','y','z']}
digits = list(digits)
if not digits: return []
res = letters[digits.pop()]
while digits:
last = letters[digits.pop()]
newres = []
for i in range(len(res)):
for j in range(len(last)):
newres.append(last[j] + res[i])
res = newres
return res
Thank you as always!
I like your channel and voice as well, lol...
this is not backtracking??? there is no code that undos your choice so i think it is more accurate to say that it just traverses the entire graph??? i think for backtracking you would want to keep a record of used values so that you can skip them and be able to reverse your choices whereas here you do not have to since you are only going deeper into the graph
A lot of these he calls backtracking really seem to be just a depth-first traversal.
Here we are modifying currStr why it is directly appended to output wy not its copy?
Time complexity is just 4^n. How come its n*4^n
same question here))
first n is the length of digits, the total of i in rec/backtrack function
if not digits:
return []
write this at the beginning of algorithm, you will get much better result
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
phoneMap = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
res, com = [], []
def backtrack(i):
if len(com) == len(digits):
res.append(''.join(com))
return
for c in phoneMap[digits[i]]:
com.append(c)
backtrack(i + 1)
com.pop()
backtrack(0)
return res
Damn I have a hard time understanding recursion stack, I mean how things will execute!
Can someone please explain why we should use
backtrack(i+1,curStr+c)
instead of
return backtrack(i+1,curStr+c) in the recursive function?😭
You can choose one of them. Both are valid solutions. For me uses backtrack(i+1, curStr+c) with res.append(curStr) is easier to think than build the combination from return backtrack().
@@mohamadilhamramadhan6354 Thank you so much for the explanation!
We can write the function outside the first function. Why are you defining it inside another function? can anyone tell advantages and disadvantages of it?
But i don't understand why time complexity is O(n*4^n)..!
thanks sir
Thank You
Thanks man
In this problem, why do we not need to pop after running backtrack? I'm so confused at the .pop() in some backtrack problems, when should we use it?
Using .pop() you are going to reduce your decision space, so you don't end up making up the same choice more than once
cause it's passed by value
The code builds a new string for every recursive call. On the other hand, when you pass in a list, that list is the same list for every recursive call.
We pop when our subset is an array we’re building and we want say 1,2 as one tree and 1,3 as another choice. We would need to pop the 2 from 1,2 so we can use the 1,3 combination. Then we continue with the rest of the numbers that same way. We’re using the same subset array so we have to pop to change the combination of numbers, or letters.
Our combinations in this particular problem are made from letters in each property in the digitToChar object. So there’s no need to pop since the next digits’s characters contain the other choices we need to add to our string.
Neetcode bro i am not satisfied with backtracking playlist
how can i think like this in a first place. I usually able to think only solution with iteration. how can I improve my problem solving with recursion .help please.
Do a bunch of recursion problems, starting from easier ones to harder, even more basic than leetcode
U a God
why can't we just use actual index of a list as digits instead of creating a map
I don't see how this is backtracking as we are not doing any .pop()?
Hello, sir, what software do you use to draw on the whiteboard, well, black board ? Thanks.
I use Paint3D
@@NeetCode thankyou
I don't understand why the time complexity is N * 4^N yet. Can someone explain it?
At each of the 4^n solutions we copy a string of length n to a list which is a O(n) operation. So for all 4^n leaf nodes in the tree we do O(n) work which is n*4^n.
This is not a backtrack soln. It's just normal recursion approach.
try to code in c++ it will be great buddy
cool - what is the intuition behind - backtrack(i + 1, curStr + c) - ? The meat of this code.
He does it a couple times in his solutions: an inner function that iterates over the input and populates a list: he does this with DFS problems where the side effect of DFS is appending the popped vertex to the resulting list. backtrack's main function is to iterate over all the list of chars for a number and append to the result which will be returned
if you take his example 23 backtrack will be called as below: for each of the letter of first digit, it will be called with letter of second digit.
SO base case will be covered when len(digit) == len(charStr) for example 2 is equal to 'ad' i.e in inner outer loop.
(inner loop 1) backtrack(1,a) (inner outer loop 2,3,4) backtrack(2,ad) backtrack(2,ae) backtrack(2,af)
(inner loop 2)backtrack(1,b) (inner outer loop 2,3,4) backtrack(2,bd) backtrack(2,be) backtrack(2,bf)
(inner loop 3)backtrack(1,c) (inner outer loop 2,3,4) backtrack(2,cd) backtrack(2,ce) backtrack(2,cf)
Nice video
which software do you use to write explanation/drawing ?
plz don't stop
should be "pqrs" for 7 instead of "qprs"
time complexity is explained so well, thank you.
isn't supposed to be only 4^n. Why are we multiplying with n
@@veliea5160 bump
Collections module makes it more effective .Am I right?
if u talking about java. then definitely...
Amazing.
I appreciate the video..but this is just a simple recursion that looks like backtracking..but this is not a backtracking.
yeah! ikr
You went from a diagram explanation straight to the code.
If you can't explain it simply, you don't really understand it yourself.
super
How that time complexity became n*4^n
What is the time complexity of the code?
bro, I hope anything you touch turns to bitcoin for you!
Nein nein nein nein!