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)

This problem can be solved by recursion, every time get 1, 2 or 3 numbers from the string, if we can get to the final of the string and have got 4 sections this mean a legal IP address.

Some example of illegal results:

For “25525511135”, 2.55.25.111 has 4 sections but doesn’t get to the last number 5.

For “0000”, 0.00.0 gets to the last number, but only has 3 sections.

There are 2 kinds of corner case:

  1. The number in the section is bigger than 255, e.g: 25.535.511.135
  2. Including usefulness 0 in the section, e.g: for “10001”, 1.00.0.1

Solution:


class Solution {
public:
        vector<string> allRes;
        void recurseEachSituations(string &res, string &s, int ptr, int index, int num)
        {
                string resTemp;
                if(s.length() - ptr > num - 1)
                {
                        switch(num)
                        {
                                case 1:
                                        resTemp = res + s[ptr];
                                        break;
                                case 2:
                                        if(s[ptr] == '0') return;//corner case 2
                                        resTemp = res + s.substr(ptr, 2);
                                        break;
                                case 3:
                                        if(stoi(s.substr(ptr,3)) > 255 || s[ptr] == '0') return;//corner case 1 and 2
                                        resTemp = res + s.substr(ptr, 3);
                        }
            
                        if(index < 4) resTemp += ".";
                        recursiveIpAdd(resTemp, s, ptr + num, index + 1);
                        resTemp.clear();
                }
        }
    
        void recursiveIpAdd(string res, string &s, int ptr, int index)
        {
        
                if(index > 4)
                {
                        if(ptr >= s.length()) allRes.push_back(res);
                        return;
                }
                if(ptr >= s.length()) return;
        
                recurseEachSituations(res, s, ptr, index, 1);//Get 1 number from string
                recurseEachSituations(res, s, ptr, index, 2);//Get 2 numbers from string
                recurseEachSituations(res, s, ptr, index, 3);//Get 3 numbers from string
        }
    
        vector<string> restoreIpAddresses(string s) {
                string res;
                recursiveIpAdd(res, s, 0, 1);
                return allRes;
        }
};
4ms

Leave a Reply

Your email address will not be published. Required fields are marked *