Restore IP address

Title Description
Given a string containing only numbers, restore it and return all possible IP address formats.
A valid IP address consists of exactly four integers (each integer is between 0 and 255), with '.' between integers separate.
Examples

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

Recursive Method
It is necessary to find out all possible restored IP addresses, so you can consider using recursive method to search all possible string segmentation methods, and filter out those that meet the requirements as the answer
Assuming that the string given in the title is s, use the recursive function dfs(segId,segStart) to search the segId segment in the IP address from the position of s[segStart], where segId ∈ {0,1,2,3,}. Since the IP fields are integers from 0 to 255, the order position segEnd of the current IP address is enumerated from small to large starting from segStart. If the requirements are met, the next section of search will be carried out recursively, and the recursive function dfs[segId+1,segEnd+1] will be called
exceptional case

Since each segment of the IP address cannot have a leading 0, if s[segStart] is equal to the character 0, the segId segment of the IP address can only be 0

In the process of recursive search, if all four ip addresses have been obtained (i.e. segId= 4) and the whole string has been traversed (i.e. segStart= |s | where | s | represents the length of string s), then this is one of the required answers and add it to the answer. At other times, if you finish traversing the string in advance, you need to end the traversal and go back to the previous step.

class Solution {
private:
    static constexpr int SEG_COUNT = 4;
private:
    vector<string> ans;
    vector<int> segments;
public:
    void dfs(const string &s,int segId,int segStart)
    {
        //If you find four ip segments and traverse the string, that is an answer
        if(segId == SEG_COUNT)
        {
            if(segStart == s.size())
            {
                string ipAddr;
                for(int i = 0;i < SEG_COUNT;i++)
                {
                    ipAddr += to_string(segments[i]);
                    if(i != SEG_COUNT-1)
                    {
                        ipAddr +=".";
                    }
                }
                ans.push_back(move(ipAddr));
            }
            return ;
        }
        //If you have traversed the string without finding the four ip addresses, you will withdraw in advance
        if(segStart == s.size())
        {
            return;
        }
        //Since there can be no leading 0, if the current number is 0, then this IP address can only be 0
        if(s[segStart] =='0')
        {
            segments[segId] = 0;
            dfs(s,segId+1,segStart+1);
        }
        //General situation
        int addr = 0;
        for(int segEnd = segStart;segEnd < s.size();segEnd++)
        {
            addr = addr * 10 + (s[segEnd]-'0');
            if(addr > 0 && addr <= 0xFF)
            {
                segments[segId] = addr;
                dfs(s,segId+1,segEnd+1);
            }
            else
            {
                break;
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);
        dfs(s,0,0);
        return ans;
    }
};

Knowledge workshop:
C++ 11 std::move()

It is to transfer the state or ownership of an object from one object to another. It is just a transfer. There is no memory relocation or memory copy. It is born for performance

c++ to_string()

The function is to convert the value into a string and return the corresponding string

resize() method of vector container

The function is to change the number of elements in the vector container

reserve() method of vector container

The function is to set the capacity of the container

Tags: leetcode

Posted by erax on Tue, 24 May 2022 21:17:18 +0300