直达链接
之前我写过一次IP地址转二进制
好吧，读完题发现好像和这题没什么关系
给一串数字中加.，返回所有的能够构成合法IP地址的结果
有点回溯的味道，但是却又和之前的排列组合不太一样：
- 其实相当于划分4个空往里填数字，但是这里每个空中的数字长度是不确定的
- 填入数字是会有额外的两个条件限制
尝试了但是不好写
class Solution {
public:
vector<string> res;
/*
* 回溯子函数，n表示：输入长度，k表示：输出长度
* index表示要填的空，只有四个空，并且每填完一个空就要加一个.，最后一个除外
*/
void backTrace(string& str,string& temp, int n, int index) {
// 只要不是第一次，就为每一次划分补一个.
if (index != 0) temp.push_back('.');
// 出口条件：等于加了三个.的长度
if (temp.size() == n + 3) {
res.push_back(temp);
return;
}
// 递归划分
int i = index;
while (i < n) {
// 对于每一个空，可以依次塞1个、2个、3个数字
for (int j = 0; j < 3; j++) {
temp.push_back(str[i]);
backTrace(str, temp, n, ++i);
}
for (int j = 0; j < 3; j++) {
temp.pop_back();
}
}
}
/*
* 给定一个由数字构成的字符串，给它们之间加点分隔，返回所有合法的IP地址
* 1. 不能有先导0
* 2. 每个部分数字范围0-255
*/
vector<string> restoreIpAddresses(string s) {
// 字符串长度范围为[1,20]，而IP地址的合法长度为[4,12]
int len = s.length();
if (len < 4 || len>12) return {};
// 将字符串划分为4个部分，回溯
string temp;
backTrace(s,temp, len, 0);
}
};
看一眼题解，思路：
相当于对一段字符串进行划分，用回溯分四段
首先我们需要一个存储所有结果的字符串数组，
其次需要一个临时容器用来存储每一次的可能结果，这里用的是一个整型数组，这个数组的长度会被定为4（4段），每一段会被转成一个整型数字（因为没有先导0，所以这么做没有问题）
我们的回溯函数参数有三个，1是原始字符串，我们需要用另一个指针参数来遍历这个字符串，最后是一个counter，用来记我们已经划分了几段（这是必要的）
回溯函数
首先我们需要定义函数的出口条件：1. 遍历完整个字符串没有遗漏 2. 已经划分四段，不多不少
-
1满足2不满足/2满足1不满足：
提前用完了还没划分四段，pass；
已经划分了四段但是还有剩，pass -
1满足2满足：
将整数数组的4段以点连接拼成一个字符串压入结果集
if (index == str.size()) {
string ipAddr;
// 虽然是4次循环，但是有可能为空，相当于清空缓存并转换为一段IP
// 这是在拼整个IP地址，4段？但是segment[i]难道不只是一个数字？后面对字符做了处理
for (int i = 0; i < SEG_COUNT; ++i) {
ipAddr += to_string(segments[i]);
// 最后一段不加.
if (i != SEG_COUNT - 1) ipAddr += '.';
}
// move函数旨在提高性能，非必要
res.push_back(move(ipAddr));
- 先导0检查
/*
* 不能有先导0，于是当遇到0的时候这一段只能是0
*/
if (str[index] == '0') {
segments[turn] = 0;
backTrace(str, turn + 1, index + 1);
}
- 1不满足，2不满足：
字符串还没遍历完，也还没划分满4段
从index标记位置开始每次压一位（连接之前的转成整数），设置为当前段值，递归下一个位置，当超过合法返回结束loop
int addr = 0;
for (int end = index; end < str.size(); ++end) {
addr = addr * 10 + (str[end] - '0');
if (addr > 0 && addr <= 0xFF) {
segments[turn] = addr;
backTrace(str, turn + 1, end + 1);
}
else break;
}
完整代码
class Solution {
private:
static constexpr int SEG_COUNT = 4;
vector<string> res;
vector<int> segments;// 保存了四段中任意一段的内容
public:
/*
* 回溯子函数，n表示：输入长度，k表示：输出长度
* index表示要填的空，只有四个空，并且每填完一个空就要加一个.，最后一个除外
*/
void backTrace(string& str, int turn, int index) {
// 出口条件：找到了4段IP地址，并且遍历完了字符串
if (turn == SEG_COUNT) {
if (index == str.size()) {
string ipAddr;
// 虽然是4次循环，但是有可能为空，相当于清空缓存并转换为一段IP
// 这是在拼整个IP地址，4段？但是segment[i]难道不只是一个数字？后面对字符做了处理
for (int i = 0; i < SEG_COUNT; ++i) {
ipAddr += to_string(segments[i]);
// 最后一段不加.
if (i != SEG_COUNT - 1) ipAddr += '.';
}
// move函数旨在提高性能，非必要
res.push_back(move(ipAddr));
}
// 如果已经生成了四段，但是没有遍历完，就不是合法的地址，舍弃
return;
}
// 没有找满4段就遍历完了
if (index == str.size()) return;
/*
* 不能有先导0，于是当遇到0的时候这一段只能是0
*/
if (str[index] == '0') {
segments[turn] = 0;
backTrace(str, turn + 1, index + 1);
}
// 一般情况
int addr = 0;
for (int end = index; end < str.size(); ++end) {
addr = addr * 10 + (str[end] - '0');
if (addr > 0 && addr <= 0xFF) {
segments[turn] = addr;
backTrace(str, turn + 1, end + 1);
}
else break;
}
}
/*
* 给定一个由数字构成的字符串，给它们之间加点分隔，返回所有合法的IP地址
* 1. 不能有先导0
* 2. 每个部分数字范围0-255
*/
vector<string> restoreIpAddresses(string s) {
// 这里其实不写长度检查，非法长度也会在后面被筛除
/*int len = s.length();
if (len < 4 || len>12) return {};*/
// 将字符串划分为4个部分，回溯
segments.resize(SEG_COUNT);
backTrace(s, 0, 0);
return res;
}
};