1. Subject requirements

leetcode 93. Restore IP address

The valid IP address consists of exactly four integers (each integer is between 0 and 255 and cannot contain leading 0). Use '.' between integers separate.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192 168@1.1 ”Is an invalid IP address.
Given a string s containing only numbers to represent an IP address, all possible valid IP addresses are returned. These addresses can be represented by inserting '.' in S To form. You cannot reorder or delete any numbers in S. You can return answers in any order.

Example 1:

Input: s = "25525511135"
Output:["255.255.11.135","255.255.111.35"]

Example 2:

Input: s = "0000"
Output:["0.0.0.0"]

Example 3:

Input: s = "1111"
Output:["1.1.1.1"]

Example 4:

Input: s = "010010"
Output:["0.10.0.10","0.100.1.0"]

Example 5:

Input: s = "101023"
Output:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Tips:

0 <= s.length <= 20
s Composed of numbers only

2. Problem solving ideas (implementation of backtracking algorithm)

Implementation algorithm: backtracking
The idea of this question is as follows:

Because the backtracking algorithm belongs to finding all qualified solutions in a range, enumerate each case and return the qualified solutions.
Therefore, this problem is realized by backtracking algorithm.

1. Set up two string arrays. res [] is used to save the results and cur [] is used to record the ip fields in the exhaustive process

cur[0] ~ ip First field of address
cur[1] ~ ip Second field of address
cur[2] ~ ip 3rd field of address
cur[3] ~ ip 4th field of address

2. The backtrack() function needs to index according to the current pointer position passed in. Since 0-255 has only three digits at most,
Therefore, you only need to judge from index index + 0 (i.e. the current bit);
indexindex+1; index-index+2; …; index+index+i-1 is the number of i bits.

For example, the ip address is 255 and index = 0
You need to enumerate the three cases of 2, 25 and 255.

(1) First, the pointer index starts with the subscript 0.
(2) The condition for the termination of backtracking is that four fields of ip have been saved in cur []. If the pointer index has just gone through all the strings at this time, it indicates that this is a legal ip address. Splice the four fields and save them in res.

(3) If there are not enough four fields in the current cur, add one character, two characters and three characters successively from the current pointer position, and continue to trace back the satisfaction.
(4) If the current pointer points to '0', judge whether it is the leading 0, and if yes, skip; Judge whether it exceeds 255. If yes, skip.
(5) Add the matching fields to cur [], and the next backtracking starts from the subscript index+i;
(6) After the backtracking, take out the current field to prepare for adding the next legal field.

3.C + + code implementation

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {

            vector<string> res; //Result array
            vector<string> cur; //Intermediate array
            if(s.size()==0)  return res;

            backtrack(s,0,cur,res);     //to flash back
            return res;
    }
    
    void backtrack(string s, int index, vector<string>&cur, vector<string>&res ){
                               //index: current pointer position
            if( cur.size()==4 ){

                if( index==s.size() )//Pointer to end of string
                {
                    string ip = cur[0] + '.' + cur[1] + '.' + cur[2] + '.' + cur[3];  
                    res.push_back(ip);
                }
                return ;
            }
            //There are not enough 4 strings in the middle array
            for(int i=1;i<=3;i++) //Each integer digit range is 0-255, with a maximum of 3 digits, starting from 1 digit to 3 digits
            { 
                if( index + i > s.size() )	//Out of working range
                    break;
                string str = s.substr(index,i);// Take i characters from the subscript index

                if( (str[0]=='0' && str.size()>1) || stoi(str)>255 )// Illegal numbers 03, 033, 256 
                    continue;
                
                cur.push_back(str);
                backtrack(s, index+i, cur, res);  //The next pointer starts with index+i
                cur.pop_back();
            }

    }

};