140 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"].

思路：最简单的就是dfs。不停地用字典里面的单词尝试去切割string s，然后把剩下的继续丢进去recurse。如果s被切归干净了，就把path给存进res里面。

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        res = []
        self.dfs(s, wordDict, '', res)
        return res

    def dfs(self, s, wordDict, cur, res):
        if not s: return [None]
        if s in wordDict: 
            res.append((cur + ' ' + s).strip())

        for word in wordDict:
            l = len(word)
            if word == s[:l]:
                self.dfs(s[l:], wordDict, cur+' '+ s[:l], res)

s = "catsanddog"
dict = ["cat", "cats", "and", "sand", "dog"]
so = Solution()
a = so.wordBreak(s, dict)
print a

然后我们再开用cache优化一下。

思路：上一种做法代码写出来还是比较简单的，可是如果你画出树形图，你会发现，好多路径被重复计算了。所以我们准备用cache来优化。这里需要注意的是，因为要用cache，所以dfs的输入就要稍微改一改，我们不切割s而是用i和j来表示截取string的哪一部分。如果i,j没有在memo里面的话那么我们就recurse去算。如果在memo里面的话，就直接返回结果。避免了重复计算的情况。

抽象出来，我们可以想象其实我们在填一个2D DP的格子。因为j恒比i大，所以我们只用填写格子的右上半部分。然后右上角那个点就是我们要输出的值（即从dp[0,len(s)]的所有解）

import collections
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        self.memo = collections.defaultdict(list)
        self.dfs(s, 0, len(s), wordDict)
        return self.memo[(0,len(s))]

    def dfs(self, s, i, j, wordDict):
        if (i, j) not in self.memo:
            if s[i:j] in wordDict:  # if in the dict add to memo
                self.memo[(i, j)] += [s[i:j]]
            for k in range(i+1,j):
                if s[i:k] in wordDict:  # take the first part
                    tail = self.dfs(s, k, j, wordDict)  # recurse rest
                    self.memo[(i,j)] += [s[i:k]+' '+t for t in tail]
        return self.memo[(i, j)]

s = "aaaaaaa"
dict = ["aaaa","aa","a"]
so = Solution()
a = so.wordBreak(s, dict)
print a

加强版：返回这个string能切割出最多个words的结果。

思路：其实就是一个top to bot的dp，不停的切割，然后只保存切割数最多的结果。memo里面存的是一个tuple，第一个int代表能切割多少个单词，后面是切割过后的结果。这样recurse下去就能得到全局最优。其实也是一个dp填格子的思想。

彩蛋：对于不能切割的情况，我们直接返回一个mission impossible哈哈（我的恶趣味），如果能有其他切割情况的话，会顶掉这个mission impossible因为我置的-1。

import collections
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        self.memo = collections.defaultdict(list)
        self.dfs(s, 0, len(s), wordDict)
        return self.memo[(0,len(s))]

    def dfs(self, s, i, j, wordDict):
        if (i, j) not in self.memo:
            res = []
            if s[i:j] in wordDict:  # if in the dict add to memo
                res += [(1, s[i:j])]
            for k in range(i+1,j):
                if s[i:k] in wordDict:  # take the first part
                    tail = self.dfs(s, k, j, wordDict)  # recurse rest
                    for t in tail:
                        res += [(1+t[0],s[i:k]+' '+t[1])]
            self.memo[(i,j)] = [max(res)] if res else [(-1,'Mission impossible')]
        return self.memo[(i, j)]

s = "aabaaaabaa"
dict = ["aaaa","aa","b"]
so = Solution()
a = so.wordBreak(s, dict)
print a

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        dp = [False]*(len(s)+1)
        dp[0]=True

        for i in range(len(s)+1):
            for w in wordDict:
                l = len(w)
                if l<=i and s[i-l:i]==w:
                    dp[i] = dp[i-l] or dp[i]
        return dp[-1]