leetcode93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
解题思路：使用dfs遍历每一种数字组合出现的情况，将IP地址分为四段，探索每一种可能性，如果在0-255的范围内，就加入结果字符串，否则则继续下一个递归，若未获得4个IP地址，则提前结束遍历，遇到0,0本身必为一个IP地址。
class Solution {
final static int IP_COUNT=4;
List<String> res = new ArrayList<String>();
int[] segments = new int[IP_COUNT];
public List<String> restoreIpAddresses(String s) {
dfs(s, 0, 0);
return res;
}
public void dfs(String s, int segId, int segStart){
//遍历结束，获得4个IP地址
if(segId==IP_COUNT){
if(segStart==s.length()){
StringBuffer ipAddr = new StringBuffer();
for(int i=0; i<IP_COUNT; i++){
ipAddr.append(segments[i]);
if(i!=IP_COUNT-1){
ipAddr.append(".");
}
}
res.add(ipAddr.toString());
}
return;
}
//未获得4个IP地址，提前结束遍历
if(segStart==s.length()){
return;
}
//遇到0,0本身必为一个IP地址
if(s.charAt(segStart)=='0'){
segments[segId] = 0;
dfs(s, segId+1, segStart+1);
}
//一般情况，遍历所有情况
int addr = 0;
for(int segEnd=segStart; segEnd<s.length(); segEnd++){
addr = addr*10 + (s.charAt(segEnd)-'0');
if(0<addr && addr<=255){
segments[segId] = addr;
dfs(s, segId+1, segEnd+1);
}
else{
break;
}
}
}
}