题目:93. 复原 IP 地址
思路
回溯法;
特别的是,用pointNum
来记录.
的数量,并且没有创建path
,而是直接在原来的strings
中插入.
;
同时,在判断子串合法性的时候,0
是合法的,01
、00
是不合法的;
代码
Method 1
class Solution {
public:
vector<string> result; //
void backtracking(string& s, int startIndex, int pointNum)
{
int i;
if(pointNum == 3)
{
string temp1 = s.substr(startIndex, s.size()-startIndex);
if(isValid(temp1))
{
result.push_back(s);
}
return;
}
for(i = startIndex; i < s.size(); i++)
{
// 判断子区间[startIndex, i]是否合法ß
string temp2 = s.substr(startIndex, i-startIndex+1);
if(isValid(temp2))
{
s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()
// pointNum++;
backtracking(s, i+2, pointNum+1);
// pointNum--;
s.erase(s.begin()+i+1);
}
// 不合法, 直接结束
else
{
break;
}
}
}
// 使用 istringstream
bool isValid(const string& s)
{
// 为空也不行
if(s.empty())
{
return false;
}
int num;
istringstream ss(s);
ss >> num;
// 0 <= num <= 255
if(!(num >= 0 && num <= 255))
{
return false;
}
// 00 也不可以
if(s.size() > 1 && s[0] == '0')
{
return false;
}
return true;
}
vector<string> restoreIpAddresses(string s)
{
result.clear();
if(s.size() < 4 || s.size() > 12)
{
return result;
}
backtracking(s, 0, 0);
return result;
}
};
回溯pointNum
用这个:backtracking(s, i+2, pointNum+1);
Method 2
class Solution {
public:
vector<string> result; //
void backtracking(string& s, int startIndex, int pointNum)
{
int i;
if(pointNum == 3)
{
string temp1 = s.substr(startIndex, s.size()-startIndex);
if(isValid(temp1))
{
result.push_back(s);
}
return;
}
for(i = startIndex; i < s.size(); i++)
{
// 判断子区间[startIndex, i]是否合法ß
string temp2 = s.substr(startIndex, i-startIndex+1);
if(isValid(temp2))
{
s.insert(s.begin()+i+1, '.'); //你为什么要加一个s.begin()
pointNum++;
backtracking(s, i+2, pointNum);
pointNum--;
s.erase(s.begin()+i+1);
}
// 不合法, 直接结束
else
{
break;
}
}
}
// 使用 istringstream
bool isValid(const string& s)
{
// 为空也不行
if(s.empty())
{
return false;
}
int num;
istringstream ss(s);
ss >> num;
// 0 <= num <= 255
if(!(num >= 0 && num <= 255))
{
return false;
}
// 00 也不可以
if(s.size() > 1 && s[0] == '0')
{
return false;
}
return true;
}
vector<string> restoreIpAddresses(string s)
{
result.clear();
if(s.size() < 4 || s.size() > 12)
{
return result;
}
backtracking(s, 0, 0);
return result;
}
};
回溯pointNum
用这个:
pointNum++;
pointNum--;
Method 3
类似于C的写法,基础方法,求出string代表的int;
bool isValid(const string& s, int start, int end)
{
int i = 0;
int num = 0;
// 一直喜欢用各种奇奇怪怪函数的carl怎么没借助C++专门的工具?
if(start > end)
{
return false;
}
// '0' 开头的数字不合法, 不包括数字'0'
if(s[start] == '0' && start != end)
{
return false;
}
for(i = start; i <= end; i++)
{
// 遇到非数字字符不合法
// if(!(s[i] >= 0 && s[i] <= 9))
if(s[i] > '9' || s[i] < '0')
{
return false;
}
num = num * 10 + (s[i] - '0');
// 如果大于255, 不合法
if(num > 255)
{
return false;
}
}
return true;
}
疑问
上述代码中使用了string.insert(s.begin()+i+1, '.')
的方式来进行插入操作,而我随便搜索的教程里没有用迭代器s.begin()
来表示插入位置的,都是直接用序号,比如string(i+1, ".")
,然而我这么写力扣反而报错了,很奇怪,很奇怪;