题目
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 地址。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "1111" 输出：["1.1.1.1"]
示例 4：
输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
解答
方法一：回溯
class Solution { public: vector<string> res; void backtracing(string& s,int startIndex,int pointNum){ if(pointNum==3){ if(isValid(s,startIndex,s.size()-1)){ res.push_back(s); } return; } for(int i=startIndex;i<s.size();i++){ if(isValid(s,startIndex,i)){ //判断 [startIndex,i] 这个区间的子串是否合法 s.insert(s.begin()+i+1,'.'); // 在i的后面插入一个逗点 pointNum++; backtracing(s,i+2,pointNum); // 插入逗点之后下一个子串的起始位置为i+2 pointNum--; // 回溯 s.erase(s.begin()+i+1); // 回溯删掉逗点 } else break; } } bool isValid(string& s,int start,int end){ if(start>end) return false; if(s[start]=='0'&&start!=end) return false; // 0开头的数字不合法 int num=0; for(int i=start;i<=end;i++){ if(s[i]<'0'||s[i]>'9') return false; // 遇到非数字字符不合法 num=num*10+s[i]-'0'; if(num>255) return false; // 如果大于255了不合法 } return true; } vector<string> restoreIpAddresses(string s) { backtracing(s,0,0); return res; } };
java
class Solution { List<String> res=new LinkedList<>(); void dfs(StringBuilder sb,int startIndex,int pointNum){ if(pointNum==3){ if(isValid(sb,startIndex,sb.length()-1)){ res.add(sb.toString()); } return; } for(int i=startIndex;i<sb.length();i++){ if(isValid(sb,startIndex,i)){ sb.insert(i+1,'.'); dfs(sb,i+2,pointNum+1); sb.deleteCharAt(i+1); } } } boolean isValid(StringBuilder sb,int l,int r){ if(l>r||r-l+1>3) return false; if(sb.charAt(l)=='0'&&l!=r) return false; Integer num=Integer.valueOf(sb.substring(l,r+1)); if(num<0||num>255) return false; return true; } public List<String> restoreIpAddresses(String s) { StringBuilder sb=new StringBuilder(s); dfs(sb,0,0); return res; } }
