Restore IP Addresses – Leetcode 93 – Python

26 thoughts on “Restore IP Addresses – Leetcode 93 – Python”

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

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

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

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

• 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

• Inner loop should be replaced by if conditions

• 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);
  
  }
  
  }
  
  }
  
  }

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

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

• 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 🙂

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

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

• at 2:50 you probably mean 3 dots

• thanks man!

• so hard

• U an IP God

• Can you explain how you got max height = 5?

• Bit confused where is back tracking happening here ?

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

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

• what is the problem in my code can someone help im not getting ay output
  class Solution {
  public:
  vector<string>res;
  void backtrack(int i,int dots,string s,string currIp)
  {
  if(dots==4&&i==s.length())
  {

  res.push_back(currIp.substr(0,currIp.length()-2));
  return;
  }
  if(dots>4)
  {
  return;
  }
  for(int j =i;j<min(i+3,11);j++)
  {
  if((stoi(s.substr(i,j+1))<256)&&(i==j||s[i]!='0'))
  {

  backtrack(j+1,dots+1,s,currIp+s.substr(i,j)+'.');
  }

  }
  }
  vector<string> restoreIpAddresses(string s) {
  if (s.length()>12)
  return res;

  backtrack(0,0,s,"");

  return res;
  }
  };

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

• thanks!

• good as always

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

• Can u do diagonal traversal of tree in java ?

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

Comments are closed.