LeetCode LCR 087. 复原 IP 地址

Categories:

题目描述
思路分析
1. 解法一：回溯（推荐）
相似题目

题目描述

✅ LCR 087. 复原 IP 地址

思路分析

解法一：回溯（推荐）

核心思路：

合法 IP 由恰好 4 段组成，每段为 0~255 的整数，且不允许前导零（”01” 非法，”0” 合法）。

用回溯（DFS）逐段枚举每段长度（1~3 位），递归分配剩余字符串：

剪枝条件（命中即跳过）：

前导零：段长度 > 1 且首字符为 '0'，不合法

数值越界：整数值 > 255，不合法

字符不足/过多：剩余字符数 < 待分段数或 > 待分段数 × 3，提前剪枝

终止条件：已选满 4 段且恰好用完所有字符时，记录结果。

推导过程：字符串长度 ≤ 12，每段最多 3 种长度，共 4 段，搜索树极小，剪枝后接近 O(1)。

复杂度分析：

时间复杂度：O(3^4) ≈ O(1)，每段最多 3 种选择，共 4 段，输入长度有上限（≤ 12）

空间复杂度：O(4)，递归深度恒为 4（分 4 段），不计结果集

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, 0, path, res);
        return res;
    }

    private void dfs(String s, int start, List<String> path, List<String> res) {
        // 已选 4 段且恰好用完字符串
        if (path.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", path));
            }
            return;
        }
        // 剪枝：剩余字符数不在合法范围内
        int remain = s.length() - start;
        int needSegs = 4 - path.size();
        if (remain < needSegs || remain > needSegs * 3) {
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > s.length()) {
                break;
            }
            String seg = s.substring(start, start + len);
            // 前导零剪枝
            if (seg.length() > 1 && seg.charAt(0) == '0') {
                break;
            }
            // 数值越界剪枝
            if (Integer.parseInt(seg) > 255) {
                break;
            }
            path.add(seg);
            dfs(s, start + len, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func restoreIpAddresses(s string) []string {
	var res []string
	var path []string

	var dfs func(start int)
	dfs = func(start int) {
		// 已选 4 段且恰好用完字符串
		if len(path) == 4 {
			if start == len(s) {
				res = append(res, strings.Join(path, "."))
			}
			return
		}
		// 剪枝：剩余字符数不在合法范围内
		remain := len(s) - start
		needSegs := 4 - len(path)
		if remain < needSegs || remain > needSegs*3 {
			return
		}
		for i := 1; i <= 3; i++ {
			if start+i > len(s) {
				break
			}
			segment := s[start : start+i]
			// 前导零剪枝
			if len(segment) > 1 && segment[0] == '0' {
				break
			}
			num, _ := strconv.Atoi(segment)
			// 数值越界剪枝
			if num > 255 {
				break
			}
			path = append(path, segment)
			dfs(start + i)
			path = path[:len(path)-1]
		}
	}

	dfs(0)
	return res
}

相似题目

题目	难度	考察点
131. 分割回文串	中等	回溯、字符串分割
17. 电话号码的字母组合	中等	回溯、枚举组合
78. 子集	中等	回溯、子集枚举
39. 组合总和	中等	回溯、剪枝
22. 括号生成	中等	回溯、合法性约束
140. 单词拆分 II	困难	回溯、字符串分割

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/43307994