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

Question

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

Answer 1

liuyubobobo 2020-04-01 04:47:01

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

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

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

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

继续加油！：）

• 提问者 v不离不弃v #1

  恩恩，老师我看了好久，大概懂了，ip.back()！=0就是判断每个部分不可以以0开头的，然后您是先考虑每部分满的情况(3个数字)，然后再依次回溯，每次从前一部分减掉最后一个字符，放入下一个部分，依次考虑，用index和ip.size（）判断是否合格，对嘛？

• 提问者 v不离不弃v #2

  网上几乎都是从每部分放入1个开始判断，再考虑2个3个，然后分析后面的剩余的部分是否合格，我感觉哎，我是想不出来。。。

• liuyubobobo 回复 提问者 v不离不弃v #3

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