数据结构与算法 -3 ：复原IP地址

石璞东

发布于 2020-05-20 00:35:49

4250

发布于 2020-05-20 00:35:49

文章被收录于专栏：石璞东 | haha石璞东 | haha

【Leetcode】题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 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

更多IP相关知识请参考如下网址：https://www.cnblogs.com/lsgxeva/p/9208298.html

思路提供

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

代码展示

复原IP地址[1]

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;
  }
};

本文总结

在本文中，我们讲解了如何将所给输入的一串数字转换成一个可用的IPV4地址，并且我们也了解部分关于IPV4的相关知识，小伙伴们学会了吗，快去实现一下吧~