专门做设计的一个网站,wordpress同步qq空间,网站建设推广图片,网页设计作业简单文章目录1 题目理解2 回溯1 题目理解
输入#xff1a;字符串s 输出#xff1a;可能的ip地址 规则#xff1a;一个有效的ip地市是一连串数字#xff0c;数字范围在0到255#xff0c;每个数字不能有前导0。例如0.1.2.201 and 192.168.1.1是有效ip地…
文章目录1 题目理解2 回溯1 题目理解
输入字符串s 输出可能的ip地址 规则一个有效的ip地市是一连串数字数字范围在0到255每个数字不能有前导0。例如0.1.2.201 and 192.168.1.1是有效ip地址。0.011.255.245不是有效地址。“192.168.1.312” and 192.1681.1也不是有效地址。
Example 1:
Input: s “25525511135” Output: [“255.255.11.135”,“255.255.111.35”] Example 2:
Input: s “0000” Output: [“0.0.0.0”] Example 3:
Input: s “1111” Output: [“1.1.1.1”] Example 4:
Input: s “010010” Output: [“0.10.0.10”,“0.100.1.0”]
2 回溯
依次处理字符串的每一位。例如s“25525511135”。 例如处理第0个2:2是一个单独的值。 处理第1个5可以是一个单独的值5也可以和前面的2合起来组成25。 处理第2个5可以是一个单独的值5也可以和前面的25合起来组成255。 … 一般就是 处理第n个字符可以是一个单独的值value1也可以和前面部分的值preValue组合成一个新的数值value2。
大致思路是这样的。在处理中会发现遇到0的情况。那就是preValue0的时候当前字符就不能和preValue组成新的值了。没有这个选项。
只有在生成的数字个数小于4个的时候才可以形成单独形成一个值value1。
class Solution {private char[] chars;private ListString result;public ListString restoreIpAddresses(String s) {if(snull || s.length()4) return new ArrayListString();this.chars s.toCharArray();result new ArrayListString();dfs(0,0,0,new ArrayListInteger());return result;}private void dfs(int index,int preValue,int numberCount,ListInteger values){if(indexchars.length){if(numberCount4){StringBuilder strb new StringBuilder();strb.append(values.get(0));for(int i1;ivalues.size();i){strb.append(.).append(values.get(i));}result.add(strb.toString());}return;}if(numberCount4) return;int value chars[index]-0;//单独成为一个值if(numberCount4) {values.add(value);dfs(index1,value,numberCount1,values);values.remove(values.size()-1);}//拼在前一个后面if(preValue0){int newValue preValue*10value;if(newValue255){values.add(newValue);dfs(index1,newValue,numberCount,values);values.remove(values.size()-1);}}}
}时间复杂度O(4∗2n)O(4*2^n)O(4∗2n) n是字符串长度。每一个字符都有2种选择。对于每一个结果要拼装回答案需要遍历数组数组长度是4。
