current position:Home>Likou 93 - Restoring IP Address [Backtracking Algorithm]

Likou 93 - Restoring IP Address [Backtracking Algorithm]

2022-08-06 18:18:18Fire_Cloud_1

一、题目分析

原题链接

题目描述

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔.

例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “[email protected]” 是 无效 IP 地址.
给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成.你 不能 重新排序或删除 s 中的任何数字.你可以按 任何 顺序返回答案.

  • 示例

输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]

输入:s = “0000”
输出:[“0.0.0.0”]

输入:s = “101023”
输出:[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

思路分析

  • First of all, according to the subject itself can see this is a related to string segmentation problem,是属于回溯算法的一种,Do not know much about the algorithm of friend can go to look at,Backtracking algorithm it isDFS(深度优先搜索)的一种,与DFS不同的是,It doesn't all the way down through,Will go back to find other solution.So the topic,As for how to divide,我画了一张图,大家一看便知
    请添加图片描述
  • 怎么样,是不是很清晰,Have some basic understanding of the subject,It follows that continue to split formed a树形结构,This is one of the data structure,Don't understand the students can go to look at.举个例子,对于第一个IP串,Already capture2,It follows that it can capture again5,或者是55,但是552就不行了,Because it is beyond the255的范围界限,And then back to step by step to determine whether or not each field can be legal,且听我慢慢道来

二、Check with solutions for multiple code

回溯三部曲

①递归函数的返回值以及参数

void backtracking(string s,int startindex,int pointnum)
  • We should consider above all is the recursive function return values and parameters,对于返回值,一般都是void,Written in some special casesint或其他类型,The first parameter is introduced to pending字符串s,而startindexIs every time for the string to the original position of the division of where to start,Because every time back all need to start from a different location,最后的pointnum指的是IPAddress need comma“.”数量.In the title is about toIPThe address is made up of four integer(每个整数位于 0 到 255 之间组成,且不能含有前导 0)组成的,Therefore can only have three most comma,The second step is that we are in,Determine the recursive function recursive export

②递归出口

if(pointnum == 3)   //3A comma said four areas
{
    
     if(judge(s,startindex,s.size()-1))    //判断IP是否合法
     {
    
         result.push_back(s);
     }
     return;
}
  • For the recursive export,Comma is as I said to3的的判断,And in the internal,You also need to judge your incoming fromstartindex起始位置到iPosition of field string is legal,Because not only is to judge the wholeIP是否合法,And for each field is also important to the judgment of the,So as to screen out the most correct and legalIP地址,怎么样,准备开始头脑风暴吧,好戏才刚刚开始,If the judge is its legal field,则将其放入result这个结果集中,它的定义是这样的
vector<string> result;
  • The words you actually see main interface function set,Look at its return value is what,It must be defined in private variable areaprivateDefine a return value with the same container to store and receive the legalIP
vector<string> restoreIpAddresses(string s)

③单层搜索的逻辑

for(int i = startindex;i < s.size(); ++i)
{
    
    if(judge(s,startindex,i))       //若是有效IP地址
    {
    
        //在其后(0-255)Insert the comma
        s.insert(s.begin() + i + 1,'.');
        pointnum++;
        backtracking(s,i + 2,pointnum);     //多加iBecause of the comma also needs to account for a place

        //回溯
        pointnum--;
        s.erase(s.begin() + i + 1);
    }
}
  • For this single search logic judgment,We can see that the cycle is fromstartindx开始的,直到字符串的末尾,To judge,那判断IPAddress is the legal function do we need to use in the whole problem?答案是的,So we want to encapsulate it into a function,Need to call it,接下来insert()Is inserted into the function insert commas after that,Before an iterator parameter is the position,begin()是起始迭代器,+ i + 1At the end of the current field,After an argument is to insert the contents of the“.”,Because insert a comma,所以pointnum就要++,So that can pass inbacktrackingRecursive function to the next layer,Because we spoke abovepointnum==3,所以这个pointnum是一直在递增的.
  • 对于startindex这个位置为什么传入i + 2我解释一下,First, because is back,Do you want to traverse to the next branch,But is is a branch of a field,Its starting position and a field is not the same,所以要i + 1,And why do you want toi + 1再+ 1呢,Because you insert a comma,这个Comma is need of a place,所以要从i + 2个位置开始遍历
  • The following function is determineIP是否合法的
bool judge(const string str,int start,int end)
{
    
   if(start > end)         //Interception of cross-border illegal
       return false;
   if(str[start] == '0' && start != end)      //开头为数字'0'不合法
       return false;
   else
   {
    
       int num = 0;
       for(int i = start;i <= end; ++i)        
       {
           //The end point must contain,Otherwise the judge dislocation will appear when chaos
           if(str[i] < '0' || str[i] > '9')        //非法数字
               return false;
           
           num = num*10 + (str[i] - '0');     
//*10Because every time integral types are bad10倍,When I went to back;-‘0’Because will character to digital
           if(num > 255)
               return false;       //If the calculated incomenum > 255,不合法
       }
   }
   return true;            //Discuss all illegal case,The rest is legal
}
  • 可以知道,判断一个IP是否合法,The return value type istrue和false,因此要设置为bool类型,对于内容,Must be take into account as much as possible of.
  • 这里的第一种情况就是start > end,Is your incoming character section crossing the line,That is not legal;
  • 第二种Is to take into account the beginning for the digital’0’的情况,The subject itself has told us,But also to consider the is a situation in which the field list to alone0This kind of,This topic also give examples,If can forget to pull up and look at the,因为0.0.0.0这种IP也是合法的,This is a special address,General in network programming can use.So return subject,这种情况就是start == end的情况,所以当start != end时,This field is string is more than one digital,Must be two and more than two,例如01,03,005之类的,These can determine its illegal
  • 对于第三种And other information in a timely manner,We need to iterate over the judge,从传入的start到end,如果碰见了str[i] < ‘0’ || str[i] > '9’的这种情况,That this number string must be illegal,Can be judged as illegal digital
  • 最后一种,We also need to consider is the title givenIPDo not cross condition,This needs us to think about,Because every time you continue to splitIPEither to split a、Two at most, that is, three,There will be no four possible,This corresponds to the us figures ofBits 10 and one hundred - bit,This extremely important,Everyone to understand this,Because three of the Numbers on the differ10倍的,Because we want to take on the10Judgment in order to,Because every time after you back into the next subsection judgment the digits must be the last time十倍,The last time the split a,Then the split two.But why use behindstr[i] - '0’呢,This is a basic operation,你想想,因为我们拿到的是一个string字符串呀,How can the string a sum,So will it into digital to,After transformation of digital if> 255Is also can be regarded as illegal,返回false
  • Finally, when finish all illegal situation judgment,That is left is legal,返回true即可,有一点要注意Is when writing the judgment function after you don't return internally to judge if the legaltrue,Because it can't judge other indications,Must be in judging all the worst case to ease backtrue.At this point do you ever feel you brainstorm again,If you should have a rest tired,To tell the whole logic reason again,For beginners of back this question is difficult to understand(Master please ignore).
num = num*10 + (str[i] - '0'); 

OK,After had said back trilogy,Are you for this problem is the overall understand the logic and the frame structure,If you don't have very clear,I here will be the figure above and continue to draw again,You can contrast on take a look
请添加图片描述

The last is the main function call

public:
    vector<string> restoreIpAddresses(string s) {
    
        result.clear();
        if(s.size() < 4 || s.size() > 12) return result;
        backtracking(s,0,0);

    	return result;
    }
}
  • 解释一下这个s.size() < 4 || s.size() > 12是什么意思,This step is a剪枝操作,Back again if you learn to better should learn to flexibly pruning,My pictures on illegal section,Imagine if these illegal piecewise minus before the recursive function call,If it is can reduce the running time again,This is actually a process of code optimization,Behind the slowly also get used to it.
  • 好,我们回归正题,Here are two kinds of extremeIP地址,Come to think of it should also consider to,There is a kind of subject has actually gives the,Count two respective number of bits used(Do not include the comma)就很清楚了,第一种是4,第二种是12,The legalIPIs certainly in between these two cases yet,就像begin和end一样,If it is more than they are at both ends of the,那就不对了,就直接return result结果即可
		1.1.1.1			192.168.255.254

三、相似题目

The more classic back if it's a way to split string problem,可以去练练手️
131.分割回文串

四、Summary and refining

Had said that power button on the Numbers for93的题目,You the backtracking algorithm have some preliminary or deepen understanding of the,But such a topic is completely not enough,Backtracking algorithm has five big kind of problem,Respectively is a combination、Cut the string、子集、Arrangement and board problem,Interested in want to understand can again go to do some correspondingLeetCode上的题目,Subsequent will continue to update about back in the class, the topic of,敬请期待.最后,Thank you for reading this article,If you have questions to ask in the comments section or direct messages,谢谢

copyright notice
author[Fire_Cloud_1],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/218/202208061758122849.html

Random recommended