Leetcode: Restore IP Addresses

93. Restore IP Addresses

My Submissions

Total Accepted: 48051 Total Submissions: 215106 Difficulty: Medium

Given a string containing only digits, restore it by returning all possible valid IP address

 combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Subscribe to see which companies asked this question

Hide Tags

 Backtracking String

BT:

o judge j<=4
o BT:
   for i=1:3
   BT(j+1);

i--for width of section, maximal 3
j--for number of sections, maximal 4;

////////////////////////////////////////////////////////

class Solution {

 public:

        void backTrac(string &s, vector<string> &result, vector<string> &tmp, int numDig, int count){

               if (count == 3){

                      string left;

                      left.assign(s, numDig, s.size()-numDig);

                      if (left.size() == 0) return;

                      else {

                            int leftInt = stoi(left);

                            if (leftInt <= 255){

                                   tmp.push_back(left);

                                   string com = tmp[0] + '.' + tmp[1] + '.' + tmp[2] + '.' + tmp[3];

                                   result.push_back(com);

                                   tmp.pop_back();

                                   return;

                            }

                      }

               }

               else {

                      for (int i = 1; i <= 3; i++){

                            //numDig += i;

                            

                            string strTmp;

                            strTmp.assign(s, numDig, i);

                            numDig += i;

                            if (numDig == s.size()){ numDig -= i; return; };//return when size of a block >3.

                            tmp.push_back(strTmp);

                            //tmp.push_back('.');

                            int intTmp = stoi(strTmp);

                            if (intTmp > 255){

                                   //tmp.pop_back();

                                   tmp.pop_back();

                                   numDig -= i;

                                   return;

                            }

                            backTrac(s, result, tmp, numDig , count + 1);

                            //tmp.pop_back();

                            tmp.pop_back();

                            numDig -= i;

                      }

               }

        }

        vector<string> restoreIpAddresses(string s) {

               string s1, s2, s3, s4;

               //boundary check

               vector<string> result;

               vector<string> tmp;

               //tmp.push_back('"');

                      int count = 0, numDig = 0;

               backTrac(s, result, tmp, numDig, count);

               return result;

               }

        };