给定一个只包含数字的字符串,复原它(在中间插入点号)并返回所有可能的 IP 地址格式,输出可能的格式的数量。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间)组成,整数之间用 ‘.’ 分隔。
示例:
输入: “25525511135”
输出: 2
说明:因为可能的IP地址包括:[“255.255.11.135”, “255.255.111.35”]
class Solution {
private:
static constexpr int SEG_COUNT = 4;
private:
vector<string> ans;
vector<int> segments;
public:
void dfs(const string& s, int segId, int segStart) {
// 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案
if (segId == SEG_COUNT) {
if (segStart == s.size()) {
string ipAddr;
for (int i = 0; i < SEG_COUNT; ++i) {
ipAddr += to_string(segments[i]);
if (i != SEG_COUNT - 1) {
ipAddr += ".";
}
}
ans.push_back(move(ipAddr));
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯
if (segStart == s.size()) {
return;
}
// 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0
if (s[segStart] == '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
}
// 一般情况,枚举每一种可能性并递归
int addr = 0;
for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
addr = addr * 10 + (s[segEnd] - '0');
if (addr > 0 && addr <= 0xFF) {
segments[segId] = addr;
dfs(s, segId + 1, segEnd + 1);
} else {
break;
}
}
}
vector<string> restoreIpAddresses(string s) {
segments.resize(SEG_COUNT);
dfs(s, 0, 0);
return ans;
}
};
版权声明:本文为Sanbai__原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。