Restore IP Address

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)

四分法

复杂度

时间 O(N^2) 空间 O(1)

思路

用三个点将字符串分成四段，验证每一段是否是有效的。我们只要控制这三个分割点就行了，注意约束条件有两个，一个是一段字符串不超过3个字母，另一个是控制好每段字符串最远结束的位置，比如第一个字符串最多延伸到倒数第4个字母。

注意

使用Integer.valueOf()时要确保所得到数不会超界。

代码

public class Solution {    public List
    
      restoreIpAddresses(String s) {        List
     
       res = new LinkedList
      
       ();        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), s2 = s.substring(i, j), s3 = s.substring(j, k), s4 = s.substring(k, s.length());                    if(isValid(s1)&&isValid(s2)&&isValid(s3)&&isValid(s4)) res.add(s1+"."+s2+"."+s3+"."+s4);                }            }        }        return res;    }        private boolean isValid(String sub){        return sub.length()<=3 && ((sub.charAt(0) != '0' && Integer.valueOf(sub) <=255) || sub.equals("0"));    }}