LeetCode93. 复原IP地址（递归）JS

描述

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

题目地址

https://leetcode-cn.com/problems/restore-ip-addresses/

题目解析

IP地址分为四段，xxx.xxx.xxx.xxx，每一段的取值为0~255(第一段不为0)，注意每一段都不超过255

代码

var restoreIpAddresses = function(str) {
  // 保存所有符合条件的IP地址
  let res = [];
  // 递归函数
  let search = (cur, sub) => {
    // 如果剩下的位数超过12位，就说明是非法的
    if(sub.length > 12) return 
    // 边界条件，已经分完一种情况了，就将它push到res中
    if(cur.length === 4 && cur.join("") === str){
      res.push(cur.join('.'))
    }else{
      // 还没分完。正常处理情况
      // 如果剩下的数字不到3个了，就按照剩下的循环；否则按照三位循环
      for(let i=0, len=Math.min(3, sub.length), tmp; i<len; i++){
        // 取出从0开始，i+1长度的子串，也就是1~len的子串
        tmp = sub.substr(0, i+1)
        // 对取出的子串验证是否合法
        if(tmp-256 < 0){  // 小于255合法
          // 将这个合法的数字格式化（去掉前面的0），递归调用，进行下一次
          search(cur.concat([tmp * 1]), sub.substr(i + 1))
        }
      }
    }
  }
  // 第一次调用
  search([], str)
  return res
};

什么是IP（来自百度百科）

IP是英文Internet Protocol的缩写，意思是“网络之间互连的协议”，也就是为计算机网络相互连接进行通信而设计的协议。在因特网中，它是能使连接到网上的所有计算机网络实现相互通信的一套规则，规定了计算机在因特网上进行通信时应当遵守的规则。任何厂家生产的计算机系统，只要遵守IP协议就可以与因特网互连互通。正是因为有了IP协议，因特网才得以迅速发展成为世界上最大的、开放的计算机通信网络。因此，IP协议也可以叫做“因特网协议”。

IP地址表示（来自于百度百科）

IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节）。IP地址通常用“点分十进制”表示成（a.b.c.d）的形式，其中，a,b,c,d都是0~255之间的十进制整数。例：点分十进IP地址（100.4.5.6），实际上是32位二进制数（01100100.00000100.00000101.00000110）。