原文链接: https://leetcode-cn.com/problems/0on3uN

中文题目

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

 

提示：

• 0 <= s.length <= 3000
• s 仅由数字组成

 

注意：本题与主站 93 题相同：https://leetcode-cn.com/problems/restore-ip-addresses/ 

通过代码

高赞题解

回溯法

首先明确一下合法的 IP 地址的条件：

1. 一个 IP 地址有四个分段
2. 每个分段表示的数值小于等于 255
3. 分段除了表示为 0 的情况以外，其他情况的第一个数字不能为 0

所以判断分段的合法性很重要，代码如下

// 判断分段合法性
bool isValidSeg(string& seg) {
    return stoi(seg) <= 255 && (seg == "0" || seg[0] != '0');
}

下面逐个扫描输入的字符串的每一个字符，通常面临两个选择。

• 第一个选择是将当前字符拼接到当前分段之后，且拼接后的分段合法。
• 第二个选择是将当前作为新的分段数字的开始，但是必须满足一个 IP 地址的分段最多只有 4 个，并且当开始一个新的分段数字时前一个分段不能为空。

可以发现解决该问题需要若干步，每一步又面临若干个选择，最后需要返回所有符合要求的结果，所以本题可以用回溯法解决。完整代码如下，helper 函数中第一个参数 i 是当前处理的字符在 s 中的下标，segI 是分段的编号，seg 是当前已经恢复的一个分段，IP 是当前已经恢复的 IP 地址。

class Solution {
private:
    // 回溯
    void helper(string& s, int i, int segI, string seg, string ip, vector<string>& ret) {
        // 当前 ip + seg 符合要求
        if (i == s.size() && segI == 3 && isValidSeg(seg)) {
            ret.push_back(ip + seg);
        }
        else if (i < s.size() && segI <= 3) {
            string temp = seg + s[i];
            // 将当前字符拼接到当前分段之后，且拼接后的分段合法
            if (isValidSeg(temp)) {
                helper(s, i + 1, segI, temp, ip, ret);
            }

            // 将当前作为新的分段数字的开始，但是必须满足一个 IP 地址的分段最多只有 4 个，
            // 并且当开始一个新的分段数字时前一个分段不能为空
            if (seg.size() > 0 && segI < 3) {
                string str{s[i]};
                helper(s, i + 1, segI + 1, str, ip + seg + ".", ret);
            }
        }
    }

    // 判断分段合法性
    bool isValidSeg(string& seg) {
        return stoi(seg) <= 255 && (seg == "0" || seg[0] != '0');
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        helper(s, 0, 0, "", "", ret);
        return ret;
    }
};

统计信息

通过次数	提交次数	AC比率
3319	5249	63.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言