问题
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
例子
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
分析
dfs，枚举各种分割的情况，如果得到的结果满足下面的所有条件，则是一个合法的IP地址：
- 字符串被3个.号分成4个部分
- 每部分的值在[0-255]范围内
- 除非等于0，否则每部分数字的开头不能是0
要点
dfs，及时裁剪不符合条件的状态
时间复杂度
O(3^3)，因为每个.号的插入位置都可以有三种选择
空间复杂度
O(1)
代码
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
dfs(res, s);
return res;
}
private:
// ip地址的格式：XXX.XXX.XXX.XXX，XXX∈[0,255]
// len表示当前ip的长度，part表示当前ip已经包含了几部分（.号将ip地址分为四部分）
void dfs(vector<string> &res, const string &s, string ip = "", int len = 0, int part = 0) {
if (part > 4) return;
if (part == 4 && len == s.size()) {
ip.pop_back();
res.push_back(ip);
return;
}
int num = 0;
// 每部分数字的开头不能是0，除非数字本身就是0
int end = min(s[len] == '0' ? 1 : 3, (int)s.size() - len);
for (int i = 0; i < end; i++) {
num = 10 * num + s[len + i] - '0';
if (num > 255) break; // 每部分数字要在[0-255]范围内
ip += s[len + i];
dfs(res, s, ip + '.', len + i + 1, part + 1);
}
}
};
