93. 复原 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 地址。

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

示例 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 = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

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

解题思路

此题与131. 分割回文串有些相似，都属于“分割”问题，所以依然可以采用“回溯算法”来解决。

通过分析ip，可以发现合法的ip具有以下特点：

ip 由4段组成(这可以作为终止判断条件)，每段之间用.隔开；
ip的每一段的长度不能超过3；
ip的每一段不能以 0 开头(除非该段的长度为 1)
ip的每一段的整数范围在0-255之间

C++

class Solution {
public:
    vector<string> result;
    string path;

    void backTracking(string s, int times) {
        // times用于记录当前的 ip 有几段，当 times = 4 时，说明已经找到一个合法的ip了
        if (times == 4) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            string str = s.substr(0, i + 1); // 当前被截取的字符串
            string ss = s.substr(i + 1); // 截取字符串后剩下的字符串
            // 剪枝，当截取后剩下的字符串的长度 大于 组成ip还需段数的3倍时，是不合理的
            if (ss.length() > (3 - times) * 3) continue;
            // 当前倍截取的字符串是否满足(1)长度小于3;(2)长度大于1时不以”0“开头;(3)数值在0-255之间。
            if ((str.length() > 3) || (str[0] == '0' && str.length() > 1) || (atoi(str.c_str()) > 255)) {
                return;
            } else {
                if (path.length() != 0) {
                    str = "." + str;
                }
                path = path.insert(path.length(), str);
                times = times + 1; // 段数 + 1
                backTracking(ss, times);
                path = path.erase(path.length() - str.length(), str.length()); // 回溯
                times = times - 1; // 回溯
            }
        }
    }


    vector<string> restoreIpAddresses(string s) {
        result.clear();
        path = "";
        if (s.length() < 4 || s.length() > 12) return result;
        backTracking(s, 0);
        return result;
    }
};

JavaScript

let path;
let result = [];

const backTracking = (s, times) => {
    if (times === 4) {
        result.push(path);
        return;
    }

    for (let i = 0; i < s.length; i++) {
        let str = s.substr(0, i + 1);
        let ss = s.substr(i + 1);
        if (ss.length > (3 - times) * 3) continue;
        if ((str.length > 3) || (str[0] === "0" && str.length > 1) || (parseInt(str) > 255)) {
            return;
        } else {
            if (path.length != 0) {
                str = "." + str;
            }
            path = path.concat(str);
            backTracking(ss, times + 1);
            path = path.substr(0, path.length - str.length); // 回溯
        }
    }
}

var restoreIpAddresses = function(s) {
    path = "";
    result = [];
    backTracking(s, 0);
    return result;
};