原题地址
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)
public class Solution { public List<String> restoreIpAddresses(String s) { ArrayList<String> list = new ArrayList<String>(); for(int i = 1 ; i <= 3 ; i++){ for(int j = 1 ; j <= 3 ; j++){ for(int k = 1 ; k <= 3 ; k++){ int m = s.length() - (i + j + k); if( m > 0 && m <= 3){ StringBuffer sb = new StringBuffer(); int addr1 = Integer.parseInt(s.substring(0, i)); int addr2 = Integer.parseInt(s.substring(i, i+j)); int addr3 = Integer.parseInt(s.substring(i+j, i+j+k)); int addr4 = Integer.parseInt(s.substring(i+j+k)); if(addr1 <= 255 && addr2 <= 255 && addr3 <= 255 && addr4 <= 255){ sb.append(addr1).append('.').append(addr2).append('.').append(addr3).append('.').append(addr4); if(sb.length() == s.length()+3) list.add(sb.toString()); } } } } } return list; } }