leetCode: Word Break I & Word Break II

题目：

Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

分析：

一开始看到这个题目，我的第一反应是要递归，但是之后感觉递归的做法估计没办法通过，然后就开始想，之后看到别人的思路之后，感觉其实还挺容易的。

解题思路：

一个字符串S，它的长度为N，如果S能够被“字典集合”（dict）中的单词拼接而成，那么所要满足的条件为：

F(0, N) = F(0, i) && F(i, j) && F(j, N);

这样子，如果我们想知道某个子串是否可由Dict中的几个单词拼接而成就可以用这样的方式得到结果（满足条件为True, 不满足条件为False）存入到一个boolean数组的对应位置上，这样子，最后boolean数组的最后一位就是F(0, N)的值，为True表示这个字符串S可由Dict中的单词拼接，否则不行！

话不多说，上AC代码！！

题目：

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

分析：

题目是跟上一题有点不一样的是，它需要把可能的所有情况都求出来，这样子的话，有了上一题的基础，我们可以在上体的基础上做一些处理就可以得到这题的答案哈。

解题思路：

这个题目是递归的一个典型的例子，有点像（M个数里面选K个数字）这个例子的变形。

举例说明：

s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

那么当检测到cat是属于dict中的话，这时候剩下的子串, "sanddog" 可能可以组成一个解。这时候我们把“cat”加入到一个解字符串(currentStr = "" )中，然后再去递归 "sanddog"这个字符串，当递归调用的字符串 s="" （即length == 0）时递归结束，证明这个解是成立的把 currentStr加入到 result中。

所有的递归结束了之后，把currentStr恢复到进入递归前的值，再继续往下判断“cats”  ... 这样一直下去直到字符串的最后一个字符!

具体的看代码哈，语言比较还是枯燥的，我觉得看着代码比较容易理解哈！

AC代码：