LeetCode93 Restore IP Addresses

问题来源leetcode93

问题描述

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

问题分析

这道题是将字符串解析成IP格式，默认给定的字符串是只包含数字的，所以就不用考虑里面的其他字符的问题了。

因为IP的特殊性，主要是每一部分都是0-255的范围，也就是每一部分的长度最多为3，最少为1。那么其实就可以考虑使用int类型就行判断。

因为IP分为4个部分，那么每一个部分作为一个int，也就是对应一个int数组，数组大小为4.

对字符串进行遍历，统计连续字符串的和，当然每添加一位需要对前面的和乘以10.

因为每位ip最多包含3个字符，所以这里需要一个循环。如果ip当前位的数字大小在0-255的范围内，那么可以认为满足要求，进入下一层递归，也就是ip位+1，进入数组的下一个元素。如果超出了这个范围，说明不符合ip的要求，结束递归。

具体代码如下

List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
    if (s == null || s.length() < 4 || s.length() > 12) {
        return res;
    }
    help(s, new int[4], 0, 0);
    return res;
}
private void help(String s,int[] nums,int index,int count){
    if(count==4){
        if(index==s.length()){
            StringBuilder sb =new StringBuilder();
            sb.append(nums[0]);
            for (int i = 1; i <4; i++) {
                sb.append('.');
                sb.append(nums[i]);
            }
            res.add(sb.toString());
        }
            return;
    }
    nums[count]=0;
    for (int i = 0; i < 3; i++) {
        if(index+i<s.length()){
            nums[count]=nums[count]*10+s.charAt(index+i)-'0';
            if(nums[count]<256){
                help(s,nums,index+1+i,count+1);
            }
            if(nums[count]==0&&i==0){
                return;
            }
        }
    }
}

LeetCode学习笔记持续更新

GitHub地址 https://github.com/yanqinghe/leetcode

CSDN博客地址 http://blog.csdn.net/yanqinghe123/article/category/7176678