题目
给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。链接。
样例
给出字符串 "25525511135"，所有可能的IP地址为：
[
"255.255.11.135",
"255.255.111.35"
]答案
直接暴力遍历就行了，只不过需要注意的是0，以及数字是不能有前缀0。
代码
class Solution {
private:
int strToInt(const string &str)
{
int ans = ;
int len = str.size();
if(len > && str[] == '')
{
return ;
}
for(int i = ; i < len; ++ i)
{
ans = (ans * + str[i] - '');
}
return ans;
}
public:
/**
* @param s the IP string
* @return All possible valid IP addresses
*/
vector<string> restoreIpAddresses(string& s) {
// Write your code here
int len = s.size();
vector<string> ans;
string result;
string first;
string second;
string third;
string fourth;
int iFirst,iSecond,iThird,iFourth;
for(int i = ;i < len - ; ++ i)
{
first.push_back(s[i]);
iFirst = strToInt(first);
if(iFirst > )
{
break;
}
second.clear();
for(int j = i + ; j < len - ; ++ j)
{
second.push_back(s[j]);
iSecond = strToInt(second);
if(iSecond > )
{
break;
}
third.clear();
for(int k = j + ;k < len - ; ++ k)
{
third.push_back(s[k]);
iThird = strToInt(third);
if(iThird > )
{
break;
}
fourth.clear();
for(int l = k + ;l < len; ++ l)
{
fourth.push_back(s[l]);
}
iFourth = strToInt(fourth);
if(iFourth <= )
{
result = first + "." + second + "." + third + "." + fourth;
ans.push_back(result);
}
}
}
}
return ans;
}
};
我自己写的字符串转数字的方法，尽管知道可以使用sstream转换或者说使用atoi，而且以前都是使用sstream，但是还是想自己动动手玩玩。