I’m sure there’s some way I’m doing it wrong but, even when I try to recreate your solution perfectly, it for some reason doesn’t seem to work. I’ve gone through it several times and, at this point, I’m not sure what to do
How do you decide when to build a decision tree with 2 choices vs. a decision tree with more than 2 choices? I ended up going the 2 choices route (put a dot at a position vs not putting a dot at a position which is a technique you have used in other backtracking problems) which has a time complexity of O(2^n)? That 2 choice solution runs slower than your O(3^n / 3^4) solution. I drew out both the decision trees for input "101023" and the O(2^n) solution has 41 total recursive calls while your O(3^n / 3^4) solution only has 30 total recursive calls. I thought O(2^n) was always faster than O(3^n / 3^4) but that doesn't seem to be the case. What am I not understanding here? Thank you so much for your videos btw.
this happened with me when i was solving Maximum length of concatenated string with all unique characters. I thought of a 2^n solution whilst the video used a better soon. However, when I solved this question I started with 2^n and reached towards 3^4. Basically, you should know the difference as to how both the decision trees are made and then you can easily visualise as to which algo to use
It's similar to saying: if (j != i && s.charAt(i) == '0') return; if we are not at the first index of our current substring, check if the first index is zero.
I love how you did a problem related to IP address from facebook after facebook outage
you can add this
if len(s)12:
return [ ]
as constraints are
0
technically you can leave just range(i, len(s)) because if it's more than i+3, if condition would cut it as invalid anyway
Actually because you are doing string slicing at each step. The time complexity is 3 ^ 4 * N where N is the length of string
Please discuss the Time complexity for backtracking solutions.
This is so difficult, I got this question in my Oracle interview today
Thank you, Neet!
thank you very much. one more problem that I fully understand now after watching your explanation:)
Thank you Neetcode! Your explanation is really clear and making sense!
I’m sure there’s some way I’m doing it wrong but, even when I try to recreate your solution perfectly, it for some reason doesn’t seem to work. I’ve gone through it several times and, at this point, I’m not sure what to do
Check if you are incrementing dots while making the recursive call to backtrack
How do you decide when to build a decision tree with 2 choices vs. a decision tree with more than 2 choices? I ended up going the 2 choices route (put a dot at a position vs not putting a dot at a position which is a technique you have used in other backtracking problems) which has a time complexity of O(2^n)? That 2 choice solution runs slower than your O(3^n / 3^4) solution. I drew out both the decision trees for input "101023" and the O(2^n) solution has 41 total recursive calls while your O(3^n / 3^4) solution only has 30 total recursive calls. I thought O(2^n) was always faster than O(3^n / 3^4) but that doesn't seem to be the case. What am I not understanding here?
Thank you so much for your videos btw.
this happened with me when i was solving Maximum length of concatenated string with all unique characters. I thought of a 2^n solution whilst the video used a better soon. However, when I solved this question I started with 2^n and reached towards 3^4. Basically, you should know the difference as to how both the decision trees are made and then you can easily visualise as to which algo to use
He made it to google, and then left.
Java Code:
:: LC All Passed ::
class Solution {
public List restoreIpAddresses(String s) {
ArrayList ans = new ArrayList();
if(s.length() > 12) return ans;
helper(s,0,0,"",ans);
return ans;
}
private void helper(String s, int i, int dots, String res, ArrayList ans){
if(dots == 4 && i == s.length()){ // Base
ans.add(res.substring(0,res.length()-1));
return;
}
if(dots > 4){
return;
}
for(int j = i; j < Math.min(i+3,s.length());j++){
int currnum = Integer.parseInt(s.substring(i,j+1));
if(currnum
Bit confused where is back tracking happening here ?
best explanation..
thx a lot, learned a lot from your channel, keep it up, bro.
good as always
Another way: O(n^4) by iterating the possible locations of the 3 dots.
U an IP God
Isnt it 3^3? you are placing 3 dots, and each dot position can have 3 choices
wow, i have no idea how i would come up with this solution in a real interview. 😔
you could have added the iterative solution too
thanks. condition dots>4 is not needed
at 2:50 you probably mean 3 dots
I think there should be 3 dots as well
The code is terminating the 4th dot which is always at the end
Inner loop should be replaced by if conditions
thanks man!
on line 21, why do we check i == j?
this makes more sense to me :
on line 21 :
len(s[i:j+1]) == 1 or s[i]!="0"
I think it's because you can have a single 0 but not any more digit after it. i == j ensures single zero.
It's similar to saying:
if (j != i && s.charAt(i) == '0') return;
if we are not at the first index of our current substring, check if the first index is zero.
This is tricky to implement correctly in the real interview
Can u do diagonal traversal of tree in java ?
what does it mean == j mean? I am not sure i understand
thanks!
Can you explain how you got max height = 5?
I think because of the call stack only 4 level deep. The dots > 4 return, prevent the call go deeper even when we not reach the end of the string.
Anybody has java code for this??? I am getting some error, when I write code like his. Must be some java error.
class Solution {
public List restoreIpAddresses(String s) {
ArrayList ans = new ArrayList();
if(s.length() > 12) return ans;
helper(s,0,0,"",ans);
return ans;
}
private void helper(String s, int i, int dots, String res, ArrayList ans){
if(dots == 4 && i == s.length()){ // Base
ans.add(res.substring(0,res.length()-1));
return;
}
if(dots > 4){
return;
}
for(int j = i; j < Math.min(i+3,s.length());j++){
int currnum = Integer.parseInt(s.substring(i,j+1));
if(currnum
so hard
your code is incorrect it should be
I agree on this
No sir, you are very very far from being dumb.
bro why are you always saying 4 dots when it is crystal clear that we need 3 dots to bifurcate string to 4 part
did you even watch the video