93. Restore IP Addresses

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

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

IP地址划分

Java：

 1 class Solution {
 2     public List<String> restoreIpAddresses(String s) {
 3         List<String> res = new ArrayList<String>() ;
 4         restoreIp(s,res,0,"",0) ;
 5         return res ;
 6     }
 7     
 8     public void restoreIp(String ip , List<String> res , int idx , String temp , int count){
 9         if (count > 4)
10             return ;
11         if (count == 4 && idx == ip.length())
12             res.add(temp) ;
13         for(int i = 1 ; i < 4 ; i++){
14             if (idx+i > ip.length())
15                 break ;
16             String s = ip.substring(idx,idx+i) ;
17             if (s.startsWith("0") && s.length() > 1)
18                 continue ;
19             if (i == 3 && Integer.parseInt(s) >= 256)
20                 continue ;
21             restoreIp(ip,res,idx+i,temp+s+(count==3?"":"."),count+1) ;
22         }
23     }
24 }