算法-回溯-14

力扣-真题-复原IP地址

IP地址， 一个数字 转换成四个， 需要用三个标点符号，
其实就是三次选择， 选择的位置不能 一样，
同时 这个标点符号 前的数字 需要满足

• 前缀不能为0 ,
• 数字 在 0 到 255 (当 字符串的长度大于3 直接break)，
• 然后 递归截止的条件是 三次选择做完 ,
• 同时需要注意 剩下的位数， 应该足够后面剩下 的数字数量， 比如 计算 第一个数字的时候， 就需要保留至少3位数 ，少了 就不可能拼成IP。
  代码如下

publicstaticList<String>restoreIpAddresses(Strings){List<String>result=newArrayList<>();getResult(0,0,s,result,"");returnresult;}publicstaticvoidgetResult(intpointNum,intindex,Strings,List<String>result,StringtemResult){if(pointNum==3){Stringsubstring=s.substring(index);if(substring.length()>1&&substring.charAt(0)=='0')return;if(substring.length()>3)return;inti=Integer.parseInt(substring);if(i>255)return;result.add(temResult+substring);return;}for(inti=index;i<s.length();i++){intsize=3-pointNum;if(size>s.length()-i-1)break;Stringtem=s.substring(index,i+1);System.out.println(tem);if(tem.length()>1&&tem.charAt(0)=='0')break;inttemNum=Integer.parseInt(tem);if(temNum>255)break;getResult(pointNum+1,i+1,s,result,temResult+tem+".");}}

复杂度

时间复杂度：O(1) - 固定的递归深度
因为对于一个IP地址，最多只能有3个点，每个点最多分割3位数字，所以递归的深度是固定的，最多只有4段，每段最多3个字符。这意味着递归的路径数量是有限的，不会随着输入字符串长度无限增长

空间复杂度：O(1) - 固定的递归深度和有限的结果数量