复原IP地址

题目

思路

• 判断是否满足IP需要满足几个条件

  • 必须要有四个数字，所以用变量count记录当前满足的个数
  • 不能有前缀0，因此需要转换为整数判断范围
  • 必须要有.我们可以根据count数量未达到4的时候添加.

  • 字符串里的数字必须全部使用完

    代码

    ```java List res = new ArrayList<>() ; public List restoreIpAddresses(String s) { if (s.length() > 12 || s.length() < 4) return res; recur(s, new StringBuilder(), 0); return res; }

    public void recur(String s, StringBuilder sb, int count) { int len = s.length(); if (len == 0 && count == 4) res.add(sb.toString()); String str = new String(s); for (int i = 1, n = 1; i < 4 && len >= i; i++, n *= 10) {

       String sub = s.substring(0, i);
       Integer num = Integer.valueOf(sub);
       if (num <= 255 && num >= n || i == 1) {
           StringBuilder nsb = new StringBuilder(sb);
           nsb.append(sub);
           if (count != 3) nsb.append(".");
           recur(s.substring(i), nsb, count + 1);
       }

    } }

class Solution {

List<String> res = new ArrayList<>() ;
public List<String> restoreIpAddresses(String s) {
    if (s.length() > 12 || s.length() < 4) return res;
    recur(s.toCharArray(), 0, new StringBuilder(), 0);
    return res;
}

public void recur(char[] arr, int index , StringBuilder sb, int count) {
    if (count == 4 && index == arr.length) res.add(sb.toString());
    if (count >= 4 || index == arr.length) return;
    int num = 0;
    for (int i = index, n = 1; i < arr.length; i++, n *= 10) {
        num = num * 10 + (arr[i] - '0'); 
        //注意大于255，小于当前位数应该有的大小时就退出
        if ((num > 255 || num < n) && i != index) break;
        StringBuilder nsb = new StringBuilder(sb);
        nsb.append(num);
        if (count < 3) nsb.append(".");
        recur(arr, i + 1, nsb, count + 1);
    }
}

} ``` 复原IP地址