Description

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)

Solution

要将地址解析成IP地址格式，也即把所给的字符串分成四段，每段长度是1-3个字符。

那么只要利用一个三重循环确定前三段的长度就能枚举所有的情况了，最坏情况也仅需枚举3×3×3=27次。

 

编程技巧方面：

1.可以利用substring方法完成对所给字符串的切割

2.由于所给字符串可能很短，枚举越界（例如枚举的第一、二、三段地址分别是2 3 2，一共8位，如果所给字符串不到8位则发生访问越界）。可以利用异常处理，直接将本次枚举continue掉，这样可以使代码更简洁易懂。而最终可以得到所枚举的每段IP地址的字符串，只要检验每段地址是否合法即可。

 

每段IP地址合法性判断的注意点：

1.每段的长度必须大于等于1，小于等于3

2.长度为3的段其数值不能大于255

3.长度大于1的段不能出现先导的0，例如“023”，而仅有“0”是合法的

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    public List<String> restoreIpAddresses(String s) {
        ArrayList<String> ret = new ArrayList<String>();
        if(s.length() < 4 || s.length() > 12) return ret;
        String[] seg = new String[4];
        for(int i = 1; i <= 3; i++){
        	for(int j = 1; j<= 3; j++){
        		for(int k = 1; k <= 3; k++){
        			try{
        				seg[0] = s.substring(0, i);
        				seg[1] = s.substring(i, i + j);
        				seg[2] = s.substring(i + j, i + j + k);
        				seg[3] = s.substring(i + j + k);
        			}catch(IndexOutOfBoundsException e){
        				continue;
        			}
        			boolean legal = true;
        			for(int u = 0; u < 4; u++){
        				int ad = 0;
        				if(seg[u].length() == 3) ad = Integer.parseInt(seg[u]);
        				if(seg[u].length() == 0 ||
        				   seg[u].length() > 3 ||
        				  (seg[u].length() > 1 && seg[u].charAt(0) == '0') ||
        				   ad > 255 )
        				{
        					legal = false;
        					break;
        				}
        			}
        			if(legal == true){
        				StringBuilder sb = new StringBuilder();
        				sb.append(seg[0]+"."+seg[1]+"."+seg[2]+"."+seg[3]);
        				ret.add(sb.toString());
        			}
        		}
        	}
        }
        return ret;
    }
}