LeetCode - 解题笔记 - 93 - Restore IP Addresses
Solution 1
一开始我以为是动态规划，后来反应过来要求输出所有的结果，那就必须要搜索了。
终止策略有：
- 已经有4个满足要求的分段，所有的数字分配完毕，找到一个答案
- 已经有4个满足要求的分段，尚有数字未分配，非有效答案（这一步可以直接替代超长字符串剪枝）
- 不足4个满足要求的分段，但所有数字分配完毕，非有效答案
搜索策略有：
- 如果当前向下搜索，第一个数字为0，那么只能将当前位作为一个分段向下搜索
- 否则，可以不断包括后续数字，直到和超过255（相对于硬性搜索三位，直接这么判断更简洁）
-
时间复杂度： O ( 3 4 × 12 ) O(3^4 imes 12) O(34×12)，原则来看搜索复杂度应该是 O ( N ! ) O(N!) O(N!)的，但是因为这道题的限制范围非常严格（最多检查12位，只能是4个分段），所以搜索深度只有4层，每层枚举量最多为3。 空间复杂度： O ( 1 ) O(1) O(1)，不考虑最终答案的占用，中间仅维护常数个状态量
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
vector<int> segments;
this->dfs(ans, segments, s, 0);
return ans;
}
private:
void dfs(vector<string> & ans, vector<int> & segments, string & s, int pos) {
if (segments.size() == 4) {
if (pos == s.size()) {
ans.emplace_back(this->makeIPAddress(segments));
}
return;
}
if (pos == s.size()) {
return;
}
if (s[pos] == 0) {
segments.push_back(0);
this->dfs(ans, segments, s, pos + 1);
segments.pop_back();
} else {
int segment = 0;
for (int offset = pos; offset < s.size(); offset++) {
segment = segment * 10 + (s[offset] - 48);
if (segment < 256) {
segments.push_back(segment);
this->dfs(ans, segments, s, offset + 1);
segments.pop_back();
} else {
break;
}
}
}
}
string makeIPAddress(vector<int> & segments) {
string ans;
for (int i = 0; i < segments.size(); i++) {
ans += to_string(segments[i]);
if (i < segments.size() - 1) {
ans += .;
}
}
return ans;
}
};
Solution 2
Solution 1的Python实现
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
ans = list()
segments = list()
def dfs(pos):
nonlocal segments, ans
if len(segments) == 4:
if pos == len(s):
ans.append(..join(segments))
return
if pos == len(s): return
if s[pos] == 0 :
segments.append(0)
dfs(pos + 1)
segments.pop()
else:
for offset in range(pos, len(s)):
if int(s[pos:offset + 1]) < 256:
segments.append(s[pos:offset + 1])
dfs(offset + 1)
segments.pop()
else: break
dfs(0)
return ans