93. Restore IP Addresses
Description
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)
Analysis
这道题要求我们从字符串中恢复出所有的标准IP，对于这种要求返回所有可能结果的题目，我们通常优先采用递归和回溯算法来解决。
我们可以从头到尾遍历字符串，观察每个字符是否符合我们的要求，至于什么样的字符能够被定义为符合要求，我们稍后讨论。每次取三个字符进行判断，判断其是否有效。
为什么每次取三个？稍有些网络基本常识的人就会知道，IPv4的IP地址由32个二进制数表示，共四部分，每部分由8位组成。所以最大也就是255。所以每次取三位进行判断。
在取字符的过程中，如果该字符符合条件，那么我们向后移动一位，以后一位为起点进行递归。否则，直接后移。
这个思路我们之前在Subsets问题中已经用过了，稍加改动即可。
下面我们讨论如何判断地址有效性的问题:
1.第一种情况:长度大于3，必然是无效地址，返回false
2.第二种情况:首位为0，但其长度大于1,比如001。
3.第三种情况:大于255
能够分析出上面三种情况，基本上就没什么问题了。代码如下：
class Solution {
bool isValidNum(string num){
if(num.size()>3||num[0]=='0'&&num.size()>1||num.empty()||stoi(num)>255)
return false;
return true;
}
void Dfs(string & str,int index,vector<string> & ipNum,vector<string> & ipComb){
if(ipNum.size()==4){
if(index==str.size()){
string ipAddr=ipNum[0];
for(int i=1;i<4;i++)
ipAddr+=("."+ipNum[i]);
ipComb.push_back(ipAddr);
}
return;
}
string curNum;
for(int i=index;i<str.size()&&i<index+3;i++){
curNum.push_back(str[i]);
if(isValidNum(curNum)){
ipNum.push_back(curNum);
Dfs(str,i+1,ipNum,ipComb);
ipNum.pop_back();
}
}
}
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ipNum;
vector<string> ipComb;
Dfs(s,0,ipNum,ipComb);
return ipComb;
}
};