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)
大意是找出所有可能的IP并返回
使用DFS算法，代码如下
/**
* 使用DFS算法
* @param s
* @return
*/
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
doRestore(result, "", s, 0);
return result;
}
private void doRestore(List<String> result, String path, String s, int deep){
/**
* s为空表示没有没有子节点了
* 题目要求计算可能的IP，符合IP格式按.分割后的结果只有4部分，可以想像成是DFS中的最大深度
*/
if(s.isEmpty() || deep == 4){
if(s.isEmpty() && deep == 4){
//表示符合要求,DFS找到了解
result.add(path.substring(1));
}
//无论是否找到解，在规定的条件下都必须返回
return ;
}
/**
* DFS递归
* 当当前值=0的时候,因为Ip不会有01这种，所以0一定是独立的一部分
*/
for(int i = 1; i <= (s.charAt(0) == '0' ? 1 : 3) && i <= s.length() ; i++){
String part = s.substring(0, i);
if(Integer.valueOf(part) <= 255){
doRestore(result, path + "." + part, s.substring(i), deep + 1);
}
}
}
