卓越职业院校建设专题网站,国内互动网站建设,企业门户网站制作,国外平台卖货文章目录题目描述二刷打卡第七天#xff5e; 也是很常考的一道题了#xff01;感觉和把数字翻译成字符串这道题很像#xff0c;也都可以用 DFS 来做
题目描述
还是定义全局的 list#xff0c;在 DFS 的过程不断维护 list递归结束的情况#xff1a;已经凑够四个数字 也是很常考的一道题了感觉和把数字翻译成字符串这道题很像也都可以用 DFS 来做
题目描述
还是定义全局的 list在 DFS 的过程不断维护 list递归结束的情况已经凑够四个数字跑完了 string 没跑完 string前导0当前数字首位为0直接凑上0并往下一个数字 DFS其他DFS情况最多3个数字并且进行255的范围判断
class Solution {char[] arr;ListString list new ArrayList();public ListString restoreIpAddresses(String s) {arr s.toCharArray();dfs(, 0, 0);return list;}public void dfs(String pre, int integerNums, int start) {// 加了四个并且跑完了 string 的情况if(start arr.length) {if(integerNums 4){list.add(pre.substring(0, pre.length() - 1));}return;}if(integerNums 4) {return;}// 首位为0直接冲不能前导0if(arr[start] 0) {pre 0;if(integerNums ! 4) {pre .;}dfs(pre, integerNums 1, start 1);return;}// 首位不为0, 最多选三个int temp 0;String tempIP pre;for(int i 0; i 3 start i arr.length; i) {// 255 判断temp temp * 10 (arr[start i] - 0);if(temp 255) {break;}tempIP arr[i start];dfs(tempIP ., integerNums 1, start i 1);}}
}二刷
思路不难但是条条框框写起来是真的麻烦。。
class Solution {ListString ans new LinkedList();char[] arr;public ListString restoreIpAddresses(String s) {arr s.toCharArray();dfs(, 0, 0);return ans;}void dfs(String s, int index, int pointCounts) {if(pointCounts 0 pointCounts 4) {s .;}if(index arr.length) {if(pointCounts 4) {ans.add(s);}return;}if(pointCounts 4) {return;}if(arr[index] 0) {dfs(s 0, index 1, pointCounts 1);}else {int num 0;String tempIP s;for(int i 0; i 3 index i arr.length; i) {num * 10;num arr[i index] - 0;tempIP arr[i index];if(num 255) {dfs(tempIP, index i 1, pointCounts 1);}}}}
}
