93. Restore IP Addresses
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)
Tags: Backtracking String
输入一个字符串，要求输出该字符串可能拆分成的ip地址形式。
思路：ipv4的地址应该是4段，每段0-255中的一个数。所以考虑4层DFS加一些剪枝条件即可。剪枝条件有：1、取3个字符串stoi作为地址时大于255；2、2位数或者3位数地址段以0开头
另外要检查第四段ip地址为0的情况，防止类似于"0000000"atoi之后也算作0的情况。
class Solution {
public:
bool dfs(string input, int number, string ipAddress, vector<string> &result){
if(input.length() == ){
return false;
}
if(number == ){
int addressNumber = stoi(input);
if(input[] == ''){
if(!(input.length() == && addressNumber == ))
return false;
}
if(addressNumber <= ){
ipAddress = ipAddress + input;
result.push_back(ipAddress);
return true;
}else{
return false;
}
}else{
if(input.length() >= ){
dfs(input.substr(), number + , ipAddress + input.substr(, ) + ".", result);
}
if(input.length() >= && input[] != ''){
dfs(input.substr(), number + , ipAddress + input.substr(, ) + ".", result);
}
if(input.length() >= && input[] != ''){
int addressNumber = stoi(input.substr(, ));
if(addressNumber <= ){
dfs(input.substr(), number + , ipAddress + input.substr(, ) + ".", result);
}
}
}
return true;
}
vector<string> restoreIpAddresses(string s) {
vector<string> result;
if(s.length() == || s.length() > ){
return result;
}
string temp = "";
dfs(s, , temp, result);
return result;
}
};