题解 | #数字字符串转化成IP地址#

方法一：递归+回溯

题设可知，IP地址是由四段数字组成的数字序列，中间使用“.”连接起来，每段数字处于[0, 255]之间。所以我们可以将问题分解为：得到上一段数字后，从余下的字符串求剩余几段的数字。

1、从字符串的起点开始，得到第一段数字，由题设可知，每一段的数字都不会超过三位数，所以遍历前三个数字；

2、下一段数字从上一段数字的后一位开始向后遍历，递归得到所有的可能性。通过对每段数字进行有效性判断，四段数字都满足有效性的是有效的IP地址，存入数组中。

时间复杂度：o(3ⁿ)

空间复杂度：o(n)

class Solution {
  private:
    // 存储所有可能的IP地址
    vector<string> res;
    // 可能的IP地址
    string nums;
  public:
    vector<string> restoreIpAddresses(string s) {
        // 特殊情况处理
        if (s.length() < 4)
            return res;

        dfs(s, 0, 0);
        return res;
    }

    void dfs(string s, int step, int idx) {
        // 存储当前段的字符
        string cur = "";

        if (step == 4) {
            if (idx == s.length())
                res.push_back(nums);
            else
                return;
        } else {
            for (int i = idx; i < idx + 3 && idx < s.length(); i++) {
                // 记录便于后续回溯
                string temp = nums;
                cur += s[i];
                int num = stoi(cur);
                // 数字在有效范围内且前置不能有多个0
                if (num <= 255 && (cur.length() == 1 || cur[0] != '0')) {
                    if (step != 3)
                        nums += cur + ".";
                    else
                        nums += cur;
                    // 递归得到下一段的IP
                    dfs(s, step + 1, i + 1);
                    // 回溯
                    nums = temp;
                }
            }
        }
    }
};

方法二：暴力迭代

暴力迭代，遍历所有的可能性将字符串分为四段数字，每段数字都符合IP地址的有效性的压入数组。

class Solution {
  private:
    vector<string> res;
  public:
    vector<string> restoreIpAddresses(string s) {
        // 特殊情况处理
        if (s.length() < 4)
            return res;

        string nums1, nums2, nums3, nums4;
		// 循环三次，遍历所有可能
        for (int i = 0; i < 3 && i < s.length() - 3; i++) {
            for (int j = i + 1; j < i + 4 && j < s.length() - 2; j++) {
                for (int k = j + 1; k < j + 4 && k < s.length() - 1; k++) {
                    nums1 = s.substr(0, i + 1);
                    nums2 = s.substr(i + 1, j - i);
                    nums3 = s.substr(j + 1, k - j);
                    nums4 = s.substr(k + 1, s.length() - k - 1);

                    if ((stoi(nums1) <= 255 && (nums1.length() == 1 || nums1[0] != '0')) &&
                            (stoi(nums2) <= 255 && (nums2.length() == 1 || nums2[0] != '0')) &&
                            (stoi(nums3) <= 255 && (nums3.length() == 1 || nums3[0] != '0')) &&
                            (stoi(nums4) <= 255 && (nums4.length() == 1 || nums4[0] != '0'))) {
                        res.push_back(nums1 + "." + nums2 + "." + nums3 + "." + nums4);
                    }
                }
            }
        }

        return res;
    }
};