?xml version="1.0" encoding="UTF-8"?
欢迎关注本人的微信公众号AI_Engine
小G同学最近准备推出LeetCode算法解题系列，为区别于AI算法，那么每一篇博文都将围绕一道leetcode原题进行解答。今天带来的是leetcode中单词拆分 II的解题思路，欢迎大家指教！
题目：
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
答案：
class Solution(object):
def wordBreak(self, input_str, word_dict):
tmp_dict = {}
return self.dfs(input_str, word_dict, tmp_dict)
def dfs(self, input_str, word_dict, tmp_dict):
if input_str in tmp_dict:
return tmp_dict[input_str]
if not input_str:
return ['']
result = []
for word in word_dict:
if input_str[:len(word)] != word: continue
sub_str_dfs = self.dfs(input_str[len(word):], word_dict, tmp_dict)
for res in sub_str_dfs:
res='%s%s' % (word, ('' if not res else ' ' + res))
result.append(res)
tmp_dict[input_str] = result
return result
思路分析：
博主一贯的思想是把复杂的问题简单化，把简单的问题都消化，所以一定是用最通俗的语言去讲述最淳朴的道理，不会像教材那样。有时候真的想问问有些作者，您把本来有趣或者简单的问题表达的如此晦涩，要怎样？讲述的直接明了一点，会怎样？！会怎样？！好了，我们开始了……
这道题本质上在考察深度优先搜索算法，俗称DFS。你可能会问：啥叫深度优先搜索啊？那我来告诉您：就好像你要找一个地方（比如某奢侈品打折的商场，但是你只知道大致的方向，而不知道具体的路线），在刚出发后发现有个AB分叉路口，你先选择A路口继续走，然后又遇到CD分叉路口，你在从CD选个路口继续走。如果选择C后发现是个死胡同，那就折回来走D路口，如果发现选择D后是悬崖，那就折回到AB分叉路口，选择B路口继续走（又回到最初的起点…)，这样把每种可能都进行尝试，然后找到那个奢侈品打折的商场（如果你的速度慢，可能已售罄）。
现在我们用一幅图再详细说明下：
这是一个有向图（我们先不讨论有向无向），那么在这个图中是如何深度优先搜索的呢？
第1步：访问A。
第2步：访问B（在访问了A之后，接下来应该访问的是A边的另一个顶点，即顶点B）
第3步：访问C（在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。我们选C）
第4步：访问E（接下来访问C的出边的另一个顶点，即顶点E）
第5步：访问D（接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D）
第6步：访问F（接下应该回溯"访问A的出边的另一个顶点F）
第7步：访问G。
因此访问顺序是：A -> B -> C -> E -> D -> F -> G
以上就是DFS的通俗理解，还不理解？V我。
那么这道题我们是怎么去分析呢？我们不妨用示例1去画一画（s = “catsanddog”，wordDict = ["cats", "dog", "sand", "and", "cat"]）：
那么现在思路很清晰了，我们从开始的时候就有2个路口：cat，cats。而选择在选择任意一个路口后可能下一次选择的类型也会不一样（比如sand，and)，如此下去，一旦s非常长，那么我们面临的选择就会非常多，是不是很麻烦？但是如果s很短，是不是就会很快给出答案。所以我们是否可以将一个很长的字符串分割成n个小字符串（把一个大问题分割成n个小问题），这就是分而治之的思想，也是一种经典的递归式解决问题方法。当面对这种需要分而治之的问题我们一定要找到2种条件：1.停止划分大问题的条件 2.最佳分割问题的条件。（我就不说出那些晦涩的名词了，大家理解就好）。现在我们就来分析下这两个条件是什么：1.这道题中让分割停止的条件就是无法分割，所以当字符串为空时，我们就停止分割。那么这行代码就很好理解了：if not input_str: return [‘'] 2.我们分割的条件其实很明显，就是当我们选择一个’路口’时，这个’路口’正好在字典中，那么除去这个’路口’剩下的字符串就是我们接下来面临的小问题（’路口’可以理解为子串）。于是乎，我们就遍历字典，看看是否可从字符串起始位置开始，分割出字典里的元素，直到遍历完字典为止。当然了，如果我们马上就发现可以分割出字典里的元素，那么剩下的子字符串就是我们进行下一轮分割的目标全量字符串了，这就要运用递归的方法了~所以这段代码应该也会比较好理解（tmp_dict是为了减少运算时间做的哈希，可以先不考虑）：
for word in word_dict:
if input_str[:len(word)] != word: continue
sub_str_dfs = self.dfs(input_str[len(word):], word_dict, tmp_dict)
最后，当我们无法对剩余字符串进行分割时，那么应将空字符串与上一轮递归中命中的字典元素进行拼接（拼接的方式根据题目要求）。但是当剩余字符串无法与字典元素匹配，那么就返回空，也就是说这个全量字符串无法根据字典进行拆分。
for res in sub_str_dfs:
res='%s%s' % (word, ('' if not res else ' ' + res))
result.append(res)
这样一来，我们就将每个小问题进行了解决，然后将所有小问题解决的结果整合后，就是整个大问题的结论了~这也是分而治之的重要思想！那么今天的分享就到这里了，希望我能坚持分享下去，也希望读者朋友们继续支持小G，提前祝大家十一快乐！
