Wednesday, 23 December 2015

LeetCode Restore IP Addresses O(n3) still accepted

LeetCode  Restore IP Addresses

class Solution {

public:

    vector<string> restoreIpAddresses(string s) {

     vector < string > ans;

     int l=s.size();

     if(l>12 || l<4)

       return ans;

     int i,j,k;

     int first,second,third,fourth;

     for(i=0;i<l-3;i++){

          string temp(s.begin(),s.begin()+i+1);

          if(temp.size()>=2 && temp[0]=='0')

           break;

          first=stoi(temp);

          if(first>255)

            break;

         for(j=i+1;j<l-2;j++){

            string temp1(s.begin()+i+1,s.begin()+j+1);

            if(temp1.size()>=2 && temp1[0]=='0')

             break;

            second=stoi(temp1);

            if(second>255)

            break;

         for(k=j+1;k<l-1;k++){

            string temp3(s.begin()+j+1,s.begin()+k+1);

            if(temp3.size()>=2 && temp3[0]=='0')

              break;

            third=stoi(temp3);

            string temp4(s.begin()+k+1,s.end());

            if(temp4.size()>=2 && temp4[0]=='0')

               continue;

            fourth=stoi(temp4);

            if(third<=255 && fourth<=255)

             {

                 string s1(s.begin(),s.end());

                 s1.insert(s1.begin()+i+1,'.');

                 s1.insert(s1.begin()+j+2,'.');

                 s1.insert(s1.begin()+k+3,'.');

                 ans.push_back(s1);

             }

          }

         }

       }

       return ans;

    }

};

No comments:

Post a Comment