Restore IP Addresses - Leetcode 93 - Python

[@worldwide6626]

I love how you did a problem related to IP address from facebook after facebook outage

[@Iamnoone56]

you can add this if len(s)12: return [ ] as constraints are 0

[@arina1193]

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

[@aditii5150]

This is so difficult, I got this question in my Oracle interview today

[@LakshyGupta]

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

[@khalmasonart]

Actually because you are doing string slicing at each step. The time complexity is 3 ^ 4 * N where N is the length of string

[@michaell8237]

Thank you Neetcode! Your explanation is really clear and making sense!

[@superfakerbros]

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

[@adityadn95]

Check if you are incrementing dots while making the recursive call to backtrack

[@shuhaoliang144]

thank you very much. one more problem that I fully understand now after watching your explanation:)

[@theunknown2090]

Bit confused where is back tracking happening here ?

[@sujithameriga7348]

Please discuss the Time complexity for backtracking solutions.

[@akhma102]

Thank you, Neet!

[@maaph1]

wow, i have no idea how i would come up with this solution in a real interview. 😔

[@ygwg6145]

Another way: O(n^4) by iterating the possible locations of the 3 dots.

[@shantipriya370]

best explanation..

[@jasonthai9647]

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.

[@abheykalia3409]

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

[@ananyaarya2465]

He made it to google, and then left.

[@edwardteach2]

U an IP God

[@starstarhaha]

thanks. condition dots>4 is not needed

[@Mcfly868]

Isnt it 3^3? you are placing 3 dots, and each dot position can have 3 choices

[@odelyaholiday9519]

at 2:50 you probably mean 3 dots

[@huseyinbarin1653]

I think there should be 3 dots as well

[@oogieboogie7028]

The code is terminating the 4th dot which is always at the end

[@QinBinHua]

thx a lot, learned a lot from your channel, keep it up, bro.

[@forceboxed]

Inner loop should be replaced by if conditions

[@skyjoe3655]

This is tricky to implement correctly in the real interview

[@陳柏仰-j5n]

good as always

[@rishabhroy5259]

you could have added the iterative solution too

[@nandinisraghavan8788]

Can u do diagonal traversal of tree in java ?

[@tonyz2203]

on line 21, why do we check i == j?

[@tonyz2203]

this makes more sense to me : on line 21 : len(s[i:j+1]) == 1 or s[i]!="0"

[@ayush03d]

I think it's because you can have a single 0 but not any more digit after it. i == j ensures single zero.

[@ayush03d]

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.

[@MuskanMall-y6d]

what does it mean == j mean? I am not sure i understand

[@nuamaaniqbal6373]

thanks man!

[@bentato]

thanks!

[@berylbose8635]

Anybody has java code for this??? I am getting some error, when I write code like his. Must be some java error.

[@KuchhBhiLab]

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

[@tigerbear3038]

Can you explain how you got max height = 5?

[@vuluongtrieu2609]

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.

[@hts2370]

so hard

[@anman1575]

your code is incorrect it should be

[@VikasShivashankara]

I agree on this

[@TheMadisonBluesBand]

He fixes it in the end

[@hanif2285]

No sir, you are very very far from being dumb.

[@jatingoswami4839]

bro why are you always saying 4 dots when it is crystal clear that we need 3 dots to bifurcate string to 4 part

[@scykl3]

did you even watch the video

[@TheMadisonBluesBand]

Are you daft