Medium

题目描述

有效的 IP 地址正好由四个整数组成，整数之间用单点分隔。每个整数都在 0 到 255（包含）之间且不能含有前导零。

例如，“0.1.2.201” 和 “192.168.1.1” 是有效的 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是无效的 IP 地址。

给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入句点来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回有效的 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

  • 1 <= s.length <= 20
  • s 仅由数字组成

解题思路

这是一个典型的回溯算法问题。我们需要在字符串中插入 3 个点，将字符串分割成 4 段，每段都必须是有效的 IP 地址段。

解题思路：

  1. 回溯法：使用递归回溯枚举所有可能的分割方案。从字符串开始位置出发，每次尝试取 1、2、3 个字符作为一段。

  2. 有效性检查：对于每一段，需要验证：

    • 数值在 0-255 范围内
    • 不能有前导零（除了单独的"0"）
    • 长度不超过3

  3. 剪枝优化：

    • 如果剩余字符数不足以构成剩余段数的最少字符，直接返回
    • 如果剩余字符数超过剩余段数的最多字符（每段最多3个），直接返回

  4. 终止条件：当分割出 4 段且用完所有字符时，找到一个有效解。

这种方法时间复杂度相对较低，因为有效的 IP 地址数量有限，每段最多 3 位数字，总的搜索空间不大。

代码实现

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        vector<string> path;
        backtrack(s, 0, path, result);
        return result;
    }
    
private:
    void backtrack(const string& s, int start, vector<string>& path, vector<string>& result) {
        // 如果已经分割出4段
        if (path.size() == 4) {
            if (start == s.length()) {
                result.push_back(path[0] + "." + path[1] + "." + path[2] + "." + path[3]);
            }
            return;
        }
        
        // 剪枝：剩余字符数不够或太多
        int remaining = s.length() - start;
        int segments = 4 - path.size();
        if (remaining < segments || remaining > segments * 3) {
            return;
        }
        
        // 尝试取1-3个字符作为一段
        for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
            string segment = s.substr(start, len);
            if (isValid(segment)) {
                path.push_back(segment);
                backtrack(s, start + len, path, result);
                path.pop_back();
            }
        }
    }
    
    bool isValid(const string& segment) {
        if (segment.empty() || segment.length() > 3) return false;
        if (segment.length() > 1 && segment[0] == '0') return false;
        int num = stoi(segment);
        return num >= 0 && num <= 255;
    }
};

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        path = []
        
        def backtrack(start):
            # 如果已经分割出4段
            if len(path) == 4:
                if start == len(s):
                    result.append('.'.join(path))
                return
            
            # 剪枝：剩余字符数不够或太多
            remaining = len(s) - start
            segments = 4 - len(path)
            if remaining < segments or remaining > segments * 3:
                return
            
            # 尝试取1-3个字符作为一段
            for length in range(1, 4):
                if start + length > len(s):
                    break
                segment = s[start:start + length]
                if self.is_valid(segment):
                    path.append(segment)
                    backtrack(start + length)
                    path.pop()
        
        backtrack(0)
        return result
    
    def is_valid(self, segment):
        if not segment or len(segment) > 3:
            return False
        if len(segment) > 1 and segment[0] == '0':
            return False
        return 0 <= int(segment) <= 255

public class Solution {
    public IList<string> RestoreIpAddresses(string s) {
        var result = new List<string>();
        var path = new List<string>();
        Backtrack(s, 0, path, result);
        return result;
    }
    
    private void Backtrack(string s, int start, List<string> path, List<string> result) {
        // 如果已经分割出4段
        if (path.Count == 4) {
            if (start == s.Length) {
                result.Add(string.Join(".", path));
            }
            return;
        }
        
        // 剪枝：剩余字符数不够或太多
        int remaining = s.Length - start;
        int segments = 4 - path.Count;
        if (remaining < segments || remaining > segments * 3) {
            return;
        }
        
        // 尝试取1-3个字符作为一段
        for (int len = 1; len <= 3 && start + len <= s.Length; len++) {
            string segment = s.Substring(start, len);
            if (IsValid(segment)) {
                path.Add(segment);
                Backtrack(s, start + len, path, result);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
    
    private bool IsValid(string segment) {
        if (string.IsNullOrEmpty(segment) || segment.Length > 3) return false;
        if (segment.Length > 1 && segment[0] == '0') return false;
        int num = int.Parse(segment);
        return num >= 0 && num <= 255;
    }
}

var restoreIpAddresses = function(s) {
    const result = [];
    
    function isValid(str) {
        if (str.length === 0 || str.length > 3) return false;
        if (str.length > 1 && str[0] === '0') return false;
        const num = parseInt(str);
        return num >= 0 && num <= 255;
    }
    
    function backtrack(start, parts) {
        if (parts.length === 4) {
            if (start === s.length) {
                result.push(parts.join('.'));
            }
            return;
        }
        
        for (let len = 1; len <= 3 && start + len <= s.length; len++) {
            const part = s.substring(start, start + len);
            if (isValid(part)) {
                parts.push(part);
                backtrack(start + len, parts);
                parts.pop();
            }
        }
    }
    
    backtrack(0, []);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(3^4) = O(81)
空间复杂度O(4) = O(1)

说明：

  • 时间复杂度：每段最多尝试3种长度，共4段，所以最多 3^4 = 81 种组合
  • 空间复杂度：递归深度最多为4，path数组最多存储4个字符串

相关题目