分析
-
本题的考点:递归回溯。
-
直接递归回溯求解即可,注意剪枝:(1)
s
还未被遍历结束,但是已经得到四个数据;(2)有前导0;(3)数值大于255;
代码
- C++
class Solution {
public:
vector<string> ans;
vector<string> restoreIpAddresses(string s) {
dfs(s, 0, 0, "");
return ans;
}
// 当前考虑到s[u],已经得到k的数据,答案存储在path中
void dfs(string &s, int u, int k, string path) {
if (u == s.size()) {
if (k == 4) {
path.pop_back(); // 去除最后的.
ans.push_back(path);
}
return;
}
if (k == 4) return; // 说明当前已经得到4个数据了
for (int i = u, t = 0; i < s.size(); i++) { // 考虑下一个需要生成的数据
if (i > u && s[u] == '0') break; // 说明有前导0
t = t * 10 + s[i] - '0';
if (t <= 255) dfs(s, i + 1, k + 1, path + to_string(t) + '.');
else break;
}
}
};
- Java
class Solution {
List<String> ans = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
dfs(s.toCharArray(), 0, 0, "");
return ans;
}
// 当前考虑到s[u],已经得到k的数据,答案存储在path中
private void dfs(char[] s, int u, int k, String path) {
if (u == s.length) {
if (k == 4) ans.add(path.substring(0, path.length() - 1));
return;
}
if (k == 4) return;
for (int i = u, t = 0; i < s.length; i++) {
if (i > u && s[u] == '0') break; // 说明有前导0
t = t * 10 + s[i] - '0';
if (t <= 255) dfs(s, i + 1, k + 1, path + t + ".");
else break;
}
}
}
时空复杂度分析
-
时间复杂度:指数级别。
-
空间复杂度:和递归深度有关。