LeetCode93 Restore IP Address

By | 16/03/2018

【题目】:

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)

【Code】:

//思路:递归于回溯

class Solution {

public://result 用来储存产生的结果,s为整个字符串,temp,start为遍历中的设置长度,count问对小块的计数

voiddfs(vector<string>&result, string &s, string temp, int start, int count) {

string sub = "";//储存子串

if (count ==3) {

if (start >= s.length() || s.length() - start >3)//到了第4个子串的时候如果长度比给的字符串本身要长或者字符串的长度减去起始的大于3直接返回为空

return ;

sub = s.substr(start);//从start位置开始后一位一直到最后一位的s的子串

if (!((sub.size() >1&& sub[0] =='0') || (atoi(sub.c_str()) >255))) {//atoi()将字符串转换成数字 故这个地方直接与数字255对比

temp += sub;

result.push_back(temp);

}

} else {

for (int i =1; i <=3&& start + i <= s.length(); i++) {//s.substr(pos, n) 截取s中从pos开始(包括0)的n个字符的子串,并返回

sub = s.substr(start, i);//每一次取出count在不大于三以内的字串然后交给sub

if (!((sub.size() >1&& sub[0] =='0') || (atoi(sub.c_str()) >255))) {//因为atoi的使用场景必须是其参数必须是char *而不是string类型所以在

dfs (result, s, temp + sub +".", start + i, count +1); //在这个地方需要使用c_str将sub这个string对象转换成char*

//if中还有对每个子串数字大小的判断

}

}

}

}

vector<string> restoreIpAddresses(string s) {

vector<string> result;

dfs(result, s, "", 0, 0);

return result;

}

};

【问题和解决办法】:

首先我们要知道电脑IP的规定法则,IP是三个点将一个字符串分成了4个部分,每个部分的范围是0~255,因为给定了一个字符串我们就要从头开始判断,首先第一个部分只有一个第二个部分只有一个,第三个部分只有一个,然后是第一个部分有一个,第二个部分有一个,第三个部分有两个然后依次类推下去,并且每次将最后一个部分跟数字3比较如果比3大,那么这个情况显然是无法成立的,如果小就可以放进字符串类型的容器当中,很显然如果我们这么做了那么会非常的暴力而且会用到相当多的循环结构时间复杂度自然就上去了,那么我能不能考虑一下递归呢,毕竟感觉可以试一下,但是递归的条件又是什么呢?递归也就是每次调用自己本身去解决问题,然后最后再向上返回值,那么为什么不能一开始就是第一个部分有3种情况,然后第二个部分也有三个情况,同理第三个部分也有三个情况,然后最后看总长度减去已经遍历的长度是不是比三大,然后再细化一点,对每一个部分进行对比是不是不是个数大于1且第一个元素为0或者数值大于255,如果可以满足就进行下一个部分的遍历如果不满足就跳过,最后到了最后一个部分的时候也就是第四个部分的时候那么就直接看长度和数值是否符合要求如果符合就直接放入容器种储存起来,这么算下来的话,我们每一次好像都需要一个储存结果的变量result,然后是目标字符串s,当前已出现部分的字符串的存储temp,记录下一个每一个的连续起始位置start和对部分的计数(从0开始到3共4个部分)并且还需要一个空的字符串变量用来存储我每个部分每次的遍历结果。

 

如果这篇文章对你有用,欢迎打赏:

发表评论