获得网站管理员密码,犀牛云做网站一年多少钱,自由设计师网站,泉州建站软件有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 ‘.’ 分隔。
例如#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址#xff0c;但是 “0.011.255.245”、“192.168.…有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。
例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
题解 题解可参考liweiwei1419和代码随想录
一、判断IP是否合规注意这块需要每分割一个数就判断这样有一个数不满足就递归终止相当于剪枝 首先字符串的长度小于 4 或者大于 12 一定不能拼凑出合法的 ip 地址 根据截取出来的字符串判断是否是合理的 ip 段这里写法比较多可以先截取再转换成 int 再判断 在0到255之间 0开头的话只能是0.0.0.0(s.charAt(0)‘0’s.length()!1,return false) 数目不等于四组即num 4用num判断而不需要用string.split()函数分割结果字符串
二、利用回溯法找分割位置
终止条件startIndexs.length()(分割位置越过数组长度说明已经得到了一个满足条件的IP),path.add(temp)这里要判断num4,由于 ip 段就 4 个段不满足不可以加入结果集每层限制istartIndex2剪枝每一个结点可以选择截取的方法只有 3 种截 1 位、截 2 位、截 3 位因此每一个结点可以生长出的分支最多只有 3 条分支和 is.length() 1获得本次分割的数组temps.substring(startIndex,i1))“.”,注意这里最后一个数字要特殊处理 2判断是否有效有效则继续进行分割即进入下一层递归 3分割数字的数目1即num 4回溯num–递归参数有 num已经分割出多少个 ip 段 startIndex截取 ip 段的起始位置 path记录从根结点到叶子结点的一个路径 temp:记录当前已经拼接得到的字符串
class Solution {public ListString path new ArrayList();//用于记录分割了几个整数已经分割了四次才可能是有效IPpublic int num0;public ListString restoreIpAddresses(String s) {//剪枝if (s.length() 4 || s.length() 12) return path; dfs(s,,0);return path;}private void dfs(String s,String temp,int startIndex){//终止if(startIndexs.length()){//判断是否有效IPif(num4) path.add(temp);return;}for(int istartIndex;istartIndex3is.length();i){//substring(startIndex,i1)的取值范围是[startIndex,i]String strs.substring(startIndex,i1);if(isValidIP(str)){//分割数字1num;//最后一个IP不需要加.if(num4) dfs(s,tempstr,i1);else dfs(s,tempstr.,i1);//回溯但tempstr.不需要回溯num--;}else{//这条递归提前终止break;}}}private boolean isValidIP(String s){//以0开头但长度不为1如023if(s.charAt(0)0s.length()!1) return false;//大小不在0-255之间int tempInteger.valueOf(s);if(temp0||temp255) return false;return true;}
}
