Restore IP Addresses - Leetcode 93 - Python

Показать описание

0:00 - Read the problem
4:30 - Drawing Explanation
10:25 - Coding Explanation

leetcode 93

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

NeetCode

Рекомендации по теме

Комментарии

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

worldwide

you can add this
if len(s)<4 or len(s)>12:
return [ ]

as constraints are
0<=s.length<=20

Iamnoone

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

arina

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

Anthony-mpmf

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

khalmasonart

The integer validation checking condition should be int(s[i:j+1]) <=255

girishmakarandthatte

Bit confused where is back tracking happening here ?

theunknown

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

shuhaoliang

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

michaell

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

superfakerbros

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. <3 Hope to see you at Google one day :)

jasonthai

Java Code:
:: LC All Passed ::

class Solution {
public List<String> restoreIpAddresses(String s) {
ArrayList<String> 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<String> 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 <= 255 && (i == j || s.charAt(i) != '0')){
helper(s, j+1, dots+1, res + s.substring(i, j+1) + ".", ans);
}
}
}
}

LakshyGupta