深度优先搜索一般用递归的方法实现,但是怎么写好一个递归程序对于我来说挺难的。
每隔一段时间写又会犯各种错误,思绪来得快也走得快,有必要记录一下。

首先用一个问题来引出 DFS:给定一个字符串,要求用空格来分割,生成它的所有可能的分割方法。
比如给定 “abc”, 那么可能的分割是
“a” “b” “c”
或者 “ab” “c”
或者 “a” “bc”

这些题目都是给一个字符串,生成符合题意要求的分割后的结果。 既然解法类似,那么代码肯定也是类似了,只是会多加一些判断条件。

我们先回到一开始的问题:如何生成所有可能的分割?

代码如下

如果我们这样调用dfs函数
dfs(0, “abcd”, tmp, result);
那么会生成8个符合要求的结果,

a, b, c, d, 
a, b, cd, 
a, bc, d, 
a, bcd, 
ab, c, d, 
ab, cd, 
abc, d, 
abcd, 

这8个结果就是字符串 “abcd” 所有可能的分割方法。

貌似文章开头的问题用这15行代码就解决了,但是,往往代码越简单,理解起来就越是困难。
文字解释起来麻烦,于是我亲自手绘一张图。
业界良心啊!!!

因为递归返回的时候,是从最底层向上的,所以我们看到的结果是:
a, b, c, d,

a, b, cd,

a, bc, d,
a, bcd,

ab, c, d,
ab, cd,
abc, d,
abcd,

这样的四段,他们分别是由递归的不同阶段(不同的循环里面)生成的结果。

现在可以生成所有可能的分割了,那么解决 Leetcode 上的那三道题就非常简单了,一个粗暴的方法就是先保存所有可能的结果,然后按照题目要求,逐个把不符合的结果剔除。

但是这种方式有一些浪费,因为 dfs 的过程中会有一些不必要的计算,比如在 Restore IP Addresses 题目里,IP 地址只会分成4段,也就是说,
192.1.681.23.1.11
这样的结果是不符合实际的,dfs不需要继续往下进行,我们需要处理一下,这个过程有个很屌的名字叫 “剪枝”。 所以代码可以这样写 :

当我们这样调用的时候 dfs(0, 4, s, tmp, result); 只是简单地加入了一个计数器,count, 每一次递归减1,把生成的字符串控制在4段。 不过这样的剪枝还是 too young too simple的,我们知道IP地址的每段大小不超过255,上面的代码仅仅控制了生成4段,并没有检查数值的大小,所以会有一些这样的结果:
192.1.68.123111
192.1.681.23111
192.1.6812.3111
192.1.68123.111
….
….

所以我们剪枝的代码还需要改进,加入判断数字大小的功能,不过方法都是类似的,我就不贴出代码了(实际是上我还没写完 =,=)

嗯,先写到这里,有灵感了再来补充~

4,423 views
Home

2 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.