【牛客】数字字符串转化成IP地址
浏览 316 | 评论 0 | 字数 1950
TTQ
2022年04月21日
  • 原题链接: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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论