leetcode: Restore IP Addresses

问题描述：

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)

原问题链接：https://leetcode.com/problems/restore-ip-addresses/

 

问题分析

　　在这个问题描述里，主要针对的是ipv4的值的情况。从给定的字符串来说，一个ip地址所对应的地址分为４个字段，每个字段对应的数值最多为３位。假定我们先考虑地址的第一个部分，那么它可以取的值为0到255之间。所以它在对应的字符串里可以取第一个字符，第一二个字符和第一到第三个字符的情况。它们对应于字符串里的子串(s.charAt(0, 1), s.charAt(0, 2), s.charAt(0, 3))。这些情况里我们还需要判断它最终解析成整数的值是否在255之内。

　　这样，对于取ip地址的第一段来说，我们只需要循环的取前面的1, 2, 3这几个字符的情况来判断就可以了。对于后面的第二、三四段来说也类似。每次在前一个的基础上取1, 2, 3这几个字符，然后再来判断。如果合格的，就将构造出来的串加入到结果列表中。

　　按照这个思路，详细的代码实现如下：

 

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<String>();
        int len = s.length();
        for(int i = 1; i < 4 && i < len - 2; i++) {
            for(int j = i + 1; j < i + 4 && j < len - 1; j++) {
                for(int k = j + 1; k < j + 4 && k < len; k++) {
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k, len);
                    if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))
                        list.add(s1 + "." + s2 + "." + s3 + "." + s4);
                }
            }
        }
        return list;
    }
    
    public boolean isValid(String s){
        if(s.length() > 3 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255)
            return false;
        return true;
    }
}