LeetCode 93. 复原IP地址

[Chocolate1999]

仰望星空的人，不应该被嘲笑

题目描述

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

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 

提示：

0 <= s.length <= 3000
s 仅由数字组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

直接看图解，显然要用回溯来做，我的做法是对于当前位置，我们可以有三种选择，选一个，选两个，还有选三个。此时就需要判断一下是不是会出现选出边界的情况。

然后对于我们选择的数字，要判断是否出现前导 0 ，同时也要看一下如果是三位数字的话，是不是会超过 255 。题目不能重复选择，于是用组合**，免去 vis 数组。

借助大佬 xiao_ben_zhu 图解

var restoreIpAddresses = function (s) {
  let res = [];
  let dfs = (cur, start) => {
    if (cur.length == 4 && start>=s.length) {
      res.push(cur.join('.'));
      return;
    }
    if(cur.length == 4 && start != s.length) return;
    for(let k=1;k<=3;k++){
      // 如果取的范围超过了字符串长度，直接剪掉
      if(start+k-1>=s.length) return;
      // 切割字符串
      let str = s.substring(start,start+k);
      if(str.length>=2 && str[0] == 0) return;
      if(str.length>=3 && +str > 255) return;
      cur.push(str);
      dfs(cur.slice(),start+k);
      // 回溯
      cur.pop();
    }
  }
  dfs([], 0);
  return res;
};

最后

文章产出不易，还望各位小伙伴们支持一波！

往期精选：

小狮子前端の笔记仓库

leetcode-javascript：LeetCode 力扣的 JavaScript 解题仓库，前端刷题路线（思维导图）

小伙伴们可以在Issues中提交自己的解题代码，🤝 欢迎Contributing，可打卡刷题，Give a ⭐️ if this project helped you!

访问超逸の博客，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退