【LeetCode】Day48复原IP地址

题目

93. 复原 IP 地址【中等】

题解

又是回溯法…

下面这句话很重要&＃xff1a;
 
回溯算法事实上就是在一个树形问题上做深度优先遍历&＃xff0c;因此 首先需要把问题转换为树形问题。

这题主要利用 $index$ 和 $start$ 两个变量控制DFS

• index为IP地址处理到第几个段了&＃xff0c;每次&＃43;1
• start是原始字符串中遍历到第几个字符

class Solution {static final int SEG_NUM&＃61;4;//IP地址四个段List<String>res&＃61;new ArrayList<>();//结果集int[] segment&＃61;new int[SEG_NUM];//IP地址,四个整数public List<String> restoreIpAddresses(String s) {int n&＃61;s.length();if(n<4||n>12)return res;dfs(s,0,0);return res;}public void dfs(String s,int index,int start){int n&＃61;s.length();//地址四个空都满了if(index&＃61;&＃61;SEG_NUM){//s遍历完了,得到新的有效地址,加入结果集if(start&＃61;&＃61;n){StringBuilder str&＃61;new StringBuilder();for(int i&＃61;0;i<SEG_NUM;i&＃43;&＃43;){str.append(segment[i]);if(i!&＃61;SEG_NUM-1)str.append(&＃39;.&＃39;);}res.add(str.toString());}return;}//IP地址四个段还没满else{//s遍历到末尾了,说明不能成为有效地址,回溯if(start&＃61;&＃61;n){return;}//处理前导0if(s.charAt(start)&＃61;&＃61;&＃39;0&＃39;){segment[index]&＃61;0;dfs(s,index&＃43;1,start&＃43;1);}//一般情况int addr&＃61;0;for(int i&＃61;start;i<n;i&＃43;&＃43;){addr&＃61;addr*10&＃43;(s.charAt(i)-&＃39;0&＃39;);//字符转整数if(addr>0&&addr<&＃61;255){segment[index]&＃61;addr;dfs(s,index&＃43;1,i&＃43;1);//确定了一个段,继续搜索下一个段}elsereturn;}}}
}


P.S. StringBuilder效率是java字符串中最高的&＃xff0c;它的append函数有N多重载形式&＃xff0c;因此可以直接添加int型变量&＃xff1a;