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 ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> result = new ArrayList<String>(); if(s.length()>12) return result; String buffer = ""; dfs(result,s,buffer,0); return result; } public boolean valid(String s){ if(s.charAt(0) == '0') return s.equals("0"); int num = Integer.parseInt(s); return num>=0 && num <=255 ; } public void dfs(ArrayList<String> result,String s, String buffer, int count){ if(count == 3 && valid(s)){ result.add(buffer+s); } for(int i = 1 ; i < 4 && i<s.length() ; i++){ String substring = s.substring(0,i); if(valid(substring)){ dfs(result,s.substring(i),buffer+substring+".",count+1); } } } }