题目地址(93. 复原 IP 地址)

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

题目描述

  1. 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
  3. 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
  5. 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
  9. 示例 1：
  11. 输入：s = "25525511135"
  12. 输出：["255.255.11.135","255.255.111.35"]
  15. 示例 2：
  17. 输入：s = "0000"
  18. 输出：["0.0.0.0"]
  21. 示例 3：
  23. 输入：s = "1111"
  24. 输出：["1.1.1.1"]
  27. 示例 4：
  29. 输入：s = "010010"
  30. 输出：["0.10.0.10","0.100.1.0"]
  33. 示例 5：
  35. 输入：s = "101023"
  36. 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
  41. 提示：
  43. 0 <= s.length <= 20
  44. s 仅由数字组成

前置知识


公司

  • 暂无

思路

image.png

关键点

  • 切割问题
  • 判断数据合法
    • 不能含有前导0
    • 不能含有除数字外的字符
    • 每段最大为255 超过即为非法
  • 循环终止的判断 不能是遍历整个字符串 而是字符串变为4段并且最后一段合法

  • 判断合法后怎么添加”.”以及回溯删除”.”

    代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         ArrayList<String> res = new ArrayList<>();
  4.         public List<String> restoreIpAddresses(String s) {
  5.             //不符合规范的直接剪枝
  6.             if (s.length() > 12 || s.length() < 4) {
  7.                 return res;
  8.             }
  9.             loop(s, 0 , 0);
  10.             return res;
  11.         }
  12.         //s 给定的字符串 startIndex 代表开始循环的位置 pointIndex代表.的数量
  13.         void loop(String s , int startIndex , int pointIndex){
  14.             //判断终止条件 IP总共4段 pointIndex为3就是最后一段
  15.             if (pointIndex == 3) {
  16.                 //判断最后一段是否合法 合法就加入返回值列表
  17.                 if (isValid(s, startIndex, s.length() - 1)) {
  18.                     res.add(s);
  19.                 }
  20.                 return;
  21.             }
  22.             //一层的循环 每次让startIndex+1知道循环完整个字符串
  23.             for (int i = startIndex; i < s.length(); i++) {
  24.                 //判断是否合法
  25.                 if (isValid(s, startIndex, i)) {
  26.                     //假设s为123 i= 0 s = 1.23
  27.                     s = s.substring(0, i+1) + "." + s.substring(i+1);
  28.                     //.的数量++
  29.                     pointIndex ++;
  30.                     //从.的后面开始下一层的递归
  31.                     loop(s, i + 2 ,pointIndex);
  32.                     //回溯
  33.                     pointIndex -- ;
  34.                     //回溯 去掉. 继续循环 下一次就是12.3
  35.                     s = s.substring(0,i+1)+s.substring(i+2);
  36.                 } else {
  37.                     //不合法就跳过本次循环
  38.                     break;
  39.                 }
  40.             }
  41.         }
  43.         //判断是否合法
  44.         boolean isValid(String s, int start, int end) {
  45.             if (start > end) {
  46.                 return false;
  47.             }
  48.             //情况1 开头数字不能为0
  49.             if (s.charAt(start) == '0' && start != end) {
  50.                 return false;
  51.             }
  52.             //情况2 不能为非数字 每段数字不能大于255
  53.             int sum = 0;
  54.             for (int i = start; i <= end; i++) {
  55.                 if (s.charAt(i) > '9' || s.charAt(i) < '0') {
  56.                     return false;
  57.                 }
  58.                 //情况3 每段数字不能大于255
  59.                 sum = sum * 10 + (s.charAt(i) - '0');
  60.                 if (sum > 255) {
  61.                     return false;
  62.                 }
  63.             }
  64.             return true;
  65.         }
  66.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：93. 复原 IP 地址 - 图2#card=math&code=O%28n%29&id=a7uQl)
  • 空间复杂度：93. 复原 IP 地址 - 图3#card=math&code=O%28n%29&id=cBN1n)