回溯题目：复原 IP 地址

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题复原 IP 地址出处93. 复原 IP 地址难度5 级题目描述要求有效 IP 地址由恰好四个整数和分隔整数的点组成。每个整数在范围0 \texttt{0}0到255 \texttt{255}255中且不能含有前导零。例如0.1.2.201 \texttt{0.1.2.201}0.1.2.201和192.168.1.1 \texttt{192.168.1.1}192.168.1.1是有效IP 地址但是0.011.255.245 \texttt{0.011.255.245}0.011.255.245、192.168.1.312 \texttt{192.168.1.312}192.168.1.312和192.1681.1 \texttt{192.1681.1}192.1681.1是无效IP 地址。给定一个只包含数字的字符串s \texttt{s}s返回通过在s \texttt{s}s中插入点可以得到的所有可能的有效 IP 地址。不能重新排序或删除s \texttt{s}s中的任何数字。可以按任意顺序返回答案。示例示例 1输入s 25525511135 \texttt{s 25525511135}s 25525511135输出[255.255.11.135,255.255.111.35] \texttt{[255.255.11.135,255.255.111.35]}[255.255.11.135,255.255.111.35]示例 2输入s 0000 \texttt{s 0000}s 0000输出[0.0.0.0] \texttt{[0.0.0.0]}[0.0.0.0]示例 3输入s 101023 \texttt{s 101023}s 101023输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3] \texttt{[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]}[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]数据范围1 ≤ s.length ≤ 20 \texttt{1} \le \texttt{s.length} \le \texttt{20}1≤s.length≤20s \texttt{s}s仅由数字组成解法思路和算法由于有效 IP 地址由4 44个整数组成因此需要在字符串s ss中插入3 33个点得到有效的 IP 地址。可以使用回溯得到所有可能的有效 IP 地址。回溯过程中需要记录当前的起始下标start \textit{start}start和片段数segmentCount \textit{segmentCount}segmentCount使用长度为4 44的数组记录每个片段对应的整数初始时start 0 \textit{start} 0start0segmentCount 0 \textit{segmentCount} 0segmentCount0。对于每个片段只有当前片段不含前导零且对应的整数在范围[ 0 , 255 ] [0, 255][0,255]中才可能是有效 IP 地址此时继续遍历后面的片段。具体做法如下。如果segmentCount 4 \textit{segmentCount} 4segmentCount4则只有当字符串s ss遍历结束时才能得到有效的 IP 地址。当start n \textit{start} nstartn时字符串s ss遍历结束根据数组中的整数生成 IP 地址添加到答案中。如果segmentCount 4 \textit{segmentCount} 4segmentCount4则当前片段对应的片段编号为segmentCount \textit{segmentCount}segmentCount。用end \textit{end}end表示当前片段的结束下标用s [ start : end ] s[\textit{start} : \textit{end}]s[start:end]表示字符串s ss的下标范围[ start , end ] [\textit{start}, \textit{end}][start,end]的子数组将end \textit{end}end从start \textit{start}start到n − 1 n - 1n−1依次遍历执行如下操作。如果s [ start : end ] s[\textit{start} : \textit{end}]s[start:end]不含前导零且对应的整数在范围[ 0 , 255 ] [0, 255][0,255]中则当前片段可能是有效 IP 地址的一个片段将当前片段对应的整数填入数组的下标segmentCount \textit{segmentCount}segmentCount处继续对下一个片段回溯下一个片段的起始下标是end 1 \textit{end} 1end1下一个片段的片段数是segmentCount 1 \textit{segmentCount} 1segmentCount1。如果s [ start : end ] s[\textit{start} : \textit{end}]s[start:end]含前导零或对应的整数不在范围[ 0 , 255 ] [0, 255][0,255]中则当前片段不可能是有效 IP 地址的一个片段如果继续将end \textit{end}end向右移动则当前片段一定不符合有效 IP 地址的规则因此结束对当前start \textit{start}start的回溯。回溯结束时即可得到所有可能的有效 IP 地址。实现方面由于有效 IP 地址的每个片段的长度都在范围[ 1 , 3 ] [1, 3][1,3]中因此有效 IP 地址的数字位数不包括点应该在范围[ 4 , 12 ] [4, 12][4,12]中。如果s ss的长度小于4 44或大于12 1212则一定不存在有效 IP 地址返回空列表。只有当s ss的长度在范围[ 4 , 12 ] [4, 12][4,12]中时才需要使用回溯得到所有可能的有效 IP 地址。代码classSolution{staticfinalintSEGMENTS4;ListStringipAddressesnewArrayListString();int[]ipArrnewint[SEGMENTS];intn;Strings;publicListStringrestoreIpAddresses(Strings){this.ns.length();this.ss;if(nSEGMENTS||n3*SEGMENTS){returnipAddresses;}backtrack(0,0);returnipAddresses;}publicvoidbacktrack(intstart,intsegmentCount){if(segmentCountSEGMENTS){if(startn){ipAddresses.add(convert(ipArr));}}else{booleanflagtrue;for(intendstart;endnflag;end){if(valid(start,end)){ipArr[segmentCount]Integer.parseInt(s.substring(start,end1));backtrack(end1,segmentCount1);}else{flagfalse;}}}}publicbooleanvalid(intstart,intend){intlengthend-start1;if(length1||length3){returnfalse;}if(length1s.charAt(start)0){returnfalse;}returnInteger.parseInt(s.substring(start,end1))255;}publicStringconvert(int[]ipArr){StringBuffersbnewStringBuffer();sb.append(ipArr[0]);for(inti1;iSEGMENTS;i){sb.append(.);sb.append(ipArr[i]);}returnsb.toString();}}复杂度分析时间复杂度O ( n 4 ) O(n^4)O(n4)其中n nn是字符串s ss的长度。由于有效 IP 地址有4 44个片段因此需要插入3 33个点插入点的方案数是O ( n 3 ) O(n^3)O(n3)每种方案需要O ( n ) O(n)O(n)的时间得到 IP 地址和将有效 IP 地址添加到答案中因此时间复杂度是O ( n 4 ) O(n^4)O(n4)。空间复杂度O ( C ) O(C)O(C)其中C CC是有效 IP 地址的片段数C 4 C 4C4。需要创建长度为C CC的数组记录每个片段对应的整数递归调用栈的层数是O ( C ) O(C)O(C)。注意返回值不计入空间复杂度。