原题链接：https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e

题目描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。 例如： 给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 0 \le n \le 120≤n≤12 要求：空间复杂度 O(n!)O(n!),时间复杂度 O(n!)O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

我选择的是在字符串里插入三个点，分割成四块进行暴力搜索，但是要特别注意两点：

1. 分割的每一块必须在0~255之间。

2. 分割的每一块不能有前导0。

   class Solution {
     public:
    /**
     *
     * @param s string字符串
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string>ans;
        for (int i = 1; i <= (s.length() >= 3 ? s.length() - 3 : 0); i++) {
            for (int j = i + 1; j <= (s.length() >= 2 ? s.length() - 2 : 0); j++) {
                for (int k = j + 1; k <= (s.length() >= 1 ? s.length() - 1 : 0); k++) {
                    string a = s.substr(0, i);
                    string b = s.substr(i, j - i);
                    string c = s.substr(j, k - j);
                    string d = s.substr(k, s.size()  - k);
                    int A = atoi(a.c_str());
                    int B = atoi(b.c_str());
                    int C = atoi(c.c_str());
                    int D = atoi(d.c_str());
                    if ((a.length() > 1 && a[0] == '0') || (b.length() > 1 && b[0] == '0') ||
                            (c.length() > 1 && c[0] == '0') || (d.length() > 1 &&
                                    d[0] == '0'))
                        continue;
                    if (A >= 0 && A <= 255 && B >= 0 && B <= 255 && C >= 0 && C <= 255 && D >= 0 &&
                            D <= 255)
                        ans.push_back(to_string(A) + "." + to_string(B) + "." + to_string(
                                     C) + "." + to_string(D));
                }
            }
        }
        return ans;
    }
   };

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/142.html
最后修改时间：2022-04-21 22:08:14
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！