2019-05-24 | 算法 | UNLOCK

复原IP

题目描述

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

示例 :

输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

基础知识补充(这里讨论的情况是IPV4地址)

首先IP从基本大类分共有五种(分别是A、B、C、D、E类网址) , 观察这五种网址发现有一个共同点 : 任何一种IP可以分为四段,每段的十进制数值均小于255,所有数字的位数总和(即字符串的长度)不超过12

看下IPV4各类地址的范围 :

  • A类地址网络号范围:1.0.0.0—126.0.0.0
  • B类地址网络号范围:128.0.0.0—191.255.0.0
  • C类地址网络号范围:192.0.0.0—223.255.255.0
  • D类地址范围:224.0.0.0—239.255.255.255
  • E类地址范围:240.0.0.0—255.255.255.254

OK,对于本题,与IP有关的基本知识就介绍到这,若大家对于IP知识想要进一步了解,推荐大家去看看ipv4地址特征及分类

思路提供

了解了基础知识补充的内容之后,是不是觉得很简单了呢,直接一种暴力的思路,使用4个for循环,每段循环遍历3次,当且仅当for循环四个变量值之和等于所给字符串长度时,对字符串进行拆分,并判断每段数字是否符合要求(对于每段的整数,只需考虑其大小是否在0-255之间即可),若符合要求,那么对已拆分好的字符串进行复原操作(即每段数字之后加上”.”即可).

Talk is cheap,show you my code

  • Python
    class Solution {
    public:
      vector<string> restoreIpAddresses(string s) {
          vector<string> res;
          for (int a = 1; a < 4; ++a) 
          for (int b = 1; b < 4; ++b) 
          for (int c = 1; c < 4; ++c) 
          for (int d = 1; d < 4; ++d) 
              if (a + b + c + d == s.size()) {
                  int A = stoi(s.substr(0, a));
                  int B = stoi(s.substr(a, b));
                  int C = stoi(s.substr(a + b, c));
                  int D = stoi(s.substr(a + b + c, d));
                  if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                      string t = to_string(A) + "." + to_string(B) + "." + to_string(C) + "." + to_string(D);
                      if (t.size() == s.size() + 3) res.push_back(t);
                  }
              }
          return res;
      }
    };
    

评论加载中