波波老师您可以说下leetcode93题的思路吗

来源：8-2 什么是回溯

v不离不弃v

2020-04-01

波波老师，看了您的代码，感觉好难想出来哇，您是先考虑3个3个的地址，然后再依次回溯考虑2个1个，但是看了之后还是不是特别明白（就是不知道您是怎么想出来这个方法的），请问您可以把您的思路和我说下么，我看网上的光判断终止条件就有很多，您就只有最后一个index==s.size()。

写回答

1回答

liuyubobobo

2020-04-01

其实就是把这个字符串分成 4 份，含有 4 个数字，看能不能合法。

我的一些终止条件放在 dfs 的过程中判断了，比如 if(next <= 255 && ip.back() != 0)

我的建议是用一个测试用例，走一遍我的程序，看看每一步递归，程序的结果是怎样的？尤其是 ip 里面，是怎么变化的？

或者你针对某一段具体代码有疑问，可以再做补充。

继续加油！：）

liuyubobobo

v不离不弃v

我的建议是，开始可以把这个问题看成两部分。第一部分，给定一个字符串，把他分割成 4 部分，有多少种方式？这是一个经典回溯问题。第二部分，给定一个包含四部分的 ip，判断这个 ip 是否合法？这个问题应该不难。加油！：）

2020-04-01

共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 2

回答 2

回答 1

回答 2

回答 1