LeetCode 93: Restore IP Addresses (Backtracking Segment Pruning)
LeetCode 93BacktrackingStringPruningToday we solve LeetCode 93 - Restore IP Addresses.
Source: https://leetcode.com/problems/restore-ip-addresses/
English
Problem Summary
Given a digit string s, return all possible valid IP addresses formed by inserting exactly three dots. Each segment must be in [0,255] and cannot contain leading zeros unless the segment itself is "0".
Key Insight
This is a fixed-depth search problem: exactly 4 segments. At each step we only try segment lengths 1..3, then prune aggressively using validity checks and remaining-length bounds.
Brute Force and Limitations
Brute force could place three dots among all positions and then validate. It works for small strings but does unnecessary invalid checks. DFS with pruning is cleaner and interview-friendly.
Optimal Algorithm Steps
1) DFS state: current index + chosen segments list.
2) If 4 segments chosen: accept only when index reaches end.
3) Prune by remaining length: if remaining chars cannot fill remaining segments (min 1 each, max 3 each), return.
4) Try length 1..3 segments from current index.
5) Reject segment if it has leading zero (length > 1 and starts with '0') or numeric value > 255.
6) Choose segment, recurse, then backtrack.
Complexity Analysis
Time: bounded by small branching at depth 4, effectively O(1) upper bound (or O(3^4) in DFS form).
Space: O(4) recursion + path (excluding output).
Common Pitfalls
- Forgetting leading-zero rule (e.g. "01" invalid).
- Accepting fewer/more than 4 segments.
- Missing remaining-length pruning, causing wasted recursion.
- Numeric parsing mistakes near 255 boundary.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private final List<String> ans = new ArrayList<>();
private final List<String> path = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
dfs(s, 0);
return ans;
}
private void dfs(String s, int idx) {
int seg = path.size();
int remainChars = s.length() - idx;
int remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg == 4) {
if (idx == s.length()) ans.add(String.join(".", path));
return;
}
for (int len = 1; len <= 3 && idx + len <= s.length(); len++) {
if (len > 1 && s.charAt(idx) == '0') break;
String part = s.substring(idx, idx + len);
int val = Integer.parseInt(part);
if (val > 255) break;
path.add(part);
dfs(s, idx + len);
path.remove(path.size() - 1);
}
}
}func restoreIpAddresses(s string) []string {
ans := []string{}
path := make([]string, 0, 4)
var dfs func(int)
dfs = func(idx int) {
seg := len(path)
remainChars := len(s) - idx
remainSeg := 4 - seg
if remainChars < remainSeg || remainChars > remainSeg*3 {
return
}
if seg == 4 {
if idx == len(s) {
ans = append(ans, strings.Join(path, "."))
}
return
}
for l := 1; l <= 3 && idx+l <= len(s); l++ {
if l > 1 && s[idx] == '0' {
break
}
part := s[idx : idx+l]
v, _ := strconv.Atoi(part)
if v > 255 {
break
}
path = append(path, part)
dfs(idx + l)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<string> ans;
vector<string> path;
vector<string> restoreIpAddresses(string s) {
dfs(s, 0);
return ans;
}
void dfs(const string& s, int idx) {
int seg = path.size();
int remainChars = (int)s.size() - idx;
int remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg == 4) {
if (idx == (int)s.size()) {
ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
}
return;
}
for (int len = 1; len <= 3 && idx + len <= (int)s.size(); ++len) {
if (len > 1 && s[idx] == '0') break;
string part = s.substr(idx, len);
int val = stoi(part);
if (val > 255) break;
path.push_back(part);
dfs(s, idx + len);
path.pop_back();
}
}
};class Solution:
def restoreIpAddresses(self, s: str) -> list[str]:
ans = []
path = []
def dfs(idx: int) -> None:
seg = len(path)
remain_chars = len(s) - idx
remain_seg = 4 - seg
if remain_chars < remain_seg or remain_chars > remain_seg * 3:
return
if seg == 4:
if idx == len(s):
ans.append(".".join(path))
return
for l in range(1, 4):
if idx + l > len(s):
break
if l > 1 and s[idx] == "0":
break
part = s[idx:idx + l]
if int(part) > 255:
break
path.append(part)
dfs(idx + l)
path.pop()
dfs(0)
return ansvar restoreIpAddresses = function(s) {
const ans = [];
const path = [];
const dfs = (idx) => {
const seg = path.length;
const remainChars = s.length - idx;
const remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg === 4) {
if (idx === s.length) ans.push(path.join('.'));
return;
}
for (let len = 1; len <= 3 && idx + len <= s.length; len++) {
if (len > 1 && s[idx] === '0') break;
const part = s.slice(idx, idx + len);
if (Number(part) > 255) break;
path.push(part);
dfs(idx + len);
path.pop();
}
};
dfs(0);
return ans;
};中文
题目概述
给定只包含数字的字符串 s，在其中插入 3 个点，返回所有合法 IP 地址。每段范围必须在 [0,255]，且除单独 "0" 外不允许前导零。
核心思路
这是固定深度（4 段）的回溯搜索。每层只尝试长度 1~3 的分段，并结合合法性和剩余长度进行强剪枝。
暴力解法与不足
暴力可以先枚举三个点位再整体校验，但会产生大量无效组合。回溯在生成过程中就筛掉非法路径，逻辑更直接。
最优算法步骤
1）DFS 状态包含：当前下标 + 已选择段列表。
2）若已选 4 段：只有当下标到达末尾才收集答案。
3）先做剩余长度剪枝：剩余字符必须能被剩余段数以 [1,3] 覆盖。
4）从当前位置尝试长度 1~3 的片段。
5）若出现前导零（长度 > 1 且首位为 0）或数值 > 255，立即跳过。
6）加入当前段，递归下一层，返回后撤销选择。
复杂度分析
时间复杂度：深度固定为 4，分支最多 3，整体可视为常数上界（或 O(3^4)）。
空间复杂度：O(4)（不含输出）。
常见陷阱
- 把 "01" 这种前导零段误判为合法。
- 没有限制必须恰好 4 段。
- 忘记剩余长度剪枝导致无效递归过多。
- 255 边界判断写错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private final List<String> ans = new ArrayList<>();
private final List<String> path = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
dfs(s, 0);
return ans;
}
private void dfs(String s, int idx) {
int seg = path.size();
int remainChars = s.length() - idx;
int remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg == 4) {
if (idx == s.length()) ans.add(String.join(".", path));
return;
}
for (int len = 1; len <= 3 && idx + len <= s.length(); len++) {
if (len > 1 && s.charAt(idx) == '0') break;
String part = s.substring(idx, idx + len);
int val = Integer.parseInt(part);
if (val > 255) break;
path.add(part);
dfs(s, idx + len);
path.remove(path.size() - 1);
}
}
}func restoreIpAddresses(s string) []string {
ans := []string{}
path := make([]string, 0, 4)
var dfs func(int)
dfs = func(idx int) {
seg := len(path)
remainChars := len(s) - idx
remainSeg := 4 - seg
if remainChars < remainSeg || remainChars > remainSeg*3 {
return
}
if seg == 4 {
if idx == len(s) {
ans = append(ans, strings.Join(path, "."))
}
return
}
for l := 1; l <= 3 && idx+l <= len(s); l++ {
if l > 1 && s[idx] == '0' {
break
}
part := s[idx : idx+l]
v, _ := strconv.Atoi(part)
if v > 255 {
break
}
path = append(path, part)
dfs(idx + l)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}class Solution {
public:
vector<string> ans;
vector<string> path;
vector<string> restoreIpAddresses(string s) {
dfs(s, 0);
return ans;
}
void dfs(const string& s, int idx) {
int seg = path.size();
int remainChars = (int)s.size() - idx;
int remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg == 4) {
if (idx == (int)s.size()) {
ans.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
}
return;
}
for (int len = 1; len <= 3 && idx + len <= (int)s.size(); ++len) {
if (len > 1 && s[idx] == '0') break;
string part = s.substr(idx, len);
int val = stoi(part);
if (val > 255) break;
path.push_back(part);
dfs(s, idx + len);
path.pop_back();
}
}
};class Solution:
def restoreIpAddresses(self, s: str) -> list[str]:
ans = []
path = []
def dfs(idx: int) -> None:
seg = len(path)
remain_chars = len(s) - idx
remain_seg = 4 - seg
if remain_chars < remain_seg or remain_chars > remain_seg * 3:
return
if seg == 4:
if idx == len(s):
ans.append(".".join(path))
return
for l in range(1, 4):
if idx + l > len(s):
break
if l > 1 and s[idx] == "0":
break
part = s[idx:idx + l]
if int(part) > 255:
break
path.append(part)
dfs(idx + l)
path.pop()
dfs(0)
return ansvar restoreIpAddresses = function(s) {
const ans = [];
const path = [];
const dfs = (idx) => {
const seg = path.length;
const remainChars = s.length - idx;
const remainSeg = 4 - seg;
if (remainChars < remainSeg || remainChars > remainSeg * 3) return;
if (seg === 4) {
if (idx === s.length) ans.push(path.join('.'));
return;
}
for (let len = 1; len <= 3 && idx + len <= s.length; len++) {
if (len > 1 && s[idx] === '0') break;
const part = s.slice(idx, idx + len);
if (Number(part) > 255) break;
path.push(part);
dfs(idx + len);
path.pop();
}
};
dfs(0);
return ans;
};
Comments