Learn how to restore IP address in one article!

[[426350]]

Recover IP address

Given a string containing only numbers, unpack it and return all possible IP address formats.

A valid IP address consists of exactly four integers (each integer is between 0 and 255 and cannot contain leading 0), separated by '.'.

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 "[email protected]" are invalid IP addresses.

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"]

hint:

• 0 <= s.length <= 3000
• s consists only of digits

Ideas

Before doing this question, it is best to do the task of splitting 131 into a palindrome string first.

I believe that when you first see this question, you will be confused.

In fact, as long as we realize that this is a cutting problem, we can use the backtracking search method to search out all possibilities for the cutting problem, which is very similar to the 131. Splitting palindrome string we just did.

The cutting problem can be abstracted into a tree structure, as shown in the figure:

Recover IP address

Back to the trilogy

• Recursive parameters

In 131. Splitting a palindrome, we mentioned that the cutting problem is similar to the combinatorial problem.

startIndex is definitely required because the segmentation cannot be repeated and records the starting position of the next layer of recursive segmentation.

For this question, we also need a variable pointNum to record the number of commas added.

So the code is as follows:

 vector<string> result; // record results
 // startIndex: the starting position of the search, pointNum: the number of commas to add
 void backtracking(string& s, int startIndex, int pointNum) {

• Recursion termination condition

The termination condition is different from that of 131. Splitting the palindrome string. This question clearly requires that it will only be divided into 4 segments, so the cutting line cannot be used as the termination condition to cut to the end, but the number of segments divided can be used as the termination condition.

pointNum indicates the number of commas. A pointNum of 3 means that the string is divided into 4 segments.

Then verify whether the fourth paragraph is legal, and if so, add it to the result set.

The code is as follows:

 if (pointNum == 3) { // When the number of commas is 3, the separation ends
 // Determine whether the fourth substring is legal, if legal, put it into result
    if (isValid(s, startIndex, s. size () - 1)) {
 result.push_back(s);
 }
 return ;
 }

• Single-layer search logic

In 131. Splitting a Palindrome String, we have already discussed how to extract substrings during loop traversal.

In the for (int i = startIndex; i < s.size(); i++) loop, the interval [startIndex, i] is the intercepted substring, and it is necessary to determine whether this substring is legal.

If it is legal, add a symbol after the string to indicate that it has been split.

If it is illegal, end the current loop, as shown in the figure where the branch is cut off:

Recover IP address

Then comes the process of recursion and backtracking:

When calling recursively, the startIndex of the next recursive layer should start from i+2 (because the separator needs to be added to the string), and the number of separators pointNum should be +1.

When backtracking, just delete the separator . that you just added, and pointNum should also be -1.

The code is as follows:

 for ( int i = startIndex; i < s. size (); i++) {
 if (isValid(s, startIndex, i)) { // Determine whether the substring in the interval [startIndex,i] is legal
 s.insert (s.begin () + i + 1 , '.' ) ; // Insert a comma after i
 pointNum++;
 backtracking(s, i + 2, pointNum); // After inserting the comma, the starting position of the next substring is i+2
 pointNum --; // backtrack  
 s.erase( s.begin () + i + 1); // Backtrack and delete the comma
 } else break; // Illegal, end the current loop directly
 }

Determine whether the substring is legal

The last step is to write a function to determine whether the rank is valid.

The following three points are mainly considered:

• The number starting with 0 is illegal.
• Non-positive integer characters are illegal in the segment
• If the rank is greater than 255, it is illegal.

The code is as follows:

 // Determine whether the number composed of string s in the left-closed and closed interval [start, end ] is legal
 bool isValid(const string& s, int start, int   end ) {
 if (start > end ) {
 return   false ;
 }
 if (s[start] == ​​'0' && start != end ) { // Numbers starting with 0 are illegal
 return   false ;
 }
 int num = 0;
 for ( int i = start; i <= end ; i++) {
 if (s[i] > '9' || s[i] < '0' ) { // Non-numeric characters are illegal
 return   false ;
 }
        num = num * 10 + (s[i] - '0' );
 if (num > 255) { // If it is greater than 255, it is illegal
 return   false ;
 }
 }
 return   true ;
 }

C++ Code

According to the backtracking algorithm, you should know this! The backtracking algorithm template given is:

 void backtracking(parameters) {
 if (termination condition) {
 Store the results;
 return ;
 } 
 
 for (select: elements in the current layer set (the number of node children in the tree is the size of the set)) {
 Processing nodes;
 backtracking(path, selection list); // recursion
 Backtracking, undoing processing results
 }
 }

You can write the following backtracking algorithm C++ code:

 class Solution {
 private:
 vector<string> result; // record results
 // startIndex: the starting position of the search, pointNum: the number of commas to add
    void backtracking(string& s, int startIndex, int pointNum) {
 if (pointNum == 3) { // When the number of commas is 3, the separation ends
 // Determine whether the fourth substring is legal, if legal, put it into result
            if (isValid(s, startIndex, s. size () - 1)) {
                result.push_back(s);
 }
 return ;
 }
 for ( int i = startIndex; i < s. size (); i++) {
 if (isValid(s, startIndex, i)) { // Determine whether the substring in the interval [startIndex,i] is legal
 s.insert (s.begin () + i + 1 , '.' ) ; // Insert a comma after i
 pointNum++;
 backtracking(s, i + 2, pointNum); // After inserting the comma, the starting position of the next substring is i+2
 pointNum --; // backtrack  
 s.erase( s.begin () + i + 1); // Backtrack and delete the comma
 } else break; // Illegal, end the current loop directly
 }
 }
 // Determine whether the number composed of string s in the left-closed and closed interval [start, end ] is legal
    bool isValid(const string& s, int start, int   end ) {
 if (start > end ) {
 return   false ;
 }
 if (s[start] == ​​'0' && start != end ) { // Numbers starting with 0 are illegal
 return   false ;
 }
 int num = 0;
 for ( int i = start; i <= end ; i++) {
 if (s[i] > '9' || s[i] < '0' ) { // Non-numeric characters are illegal
 return   false ;
 }
            num = num * 10 + (s[i] - '0' );
 if (num > 255) { // If it is greater than 255, it is illegal
 return   false ;
 }
 }
 return   true ;
 }
 public :
    vector<string> restoreIpAddresses(string s) {
 result.clear();
 if ( s.size () > 12) return result; // It is considered pruning
        backtracking(s, 0, 0);
 return result;
 }
 };

Summarize

This question covers all the difficulties in splitting strings that I listed in 131. Splitting palindromes.

In addition, this question also requires you to manipulate the string to add commas as separators and verify the legitimacy of the interval.

It can be said to be an enhanced version of 131. Split palindrome.

In the tree structure diagram of this article, I have drawn out the detailed analysis ideas. I believe that everyone will have a clearer mind after reading it!

This article is reprinted from the WeChat public account "Code Random Thoughts", which can be followed through the following QR code. To reprint this article, please contact the Code Random Thoughts public account.