Word Break

此题是要求判断字符串s是否能被字典里面的词完整拆分，字典的词可以无限次使用

思路：

这道题一开始的想法是认为是一个区间类动态规划从两边分别拆词，然后不断从大到小递归到最后没有字符串就可以判断，但是后来发现实现上在区间的判定上有问题，且对于LeetCode上面最大的那个全是a的case效果明显不理想。后来参考博客上面的做法发现其实就是一道很简单的接龙型DP，只需要根据字符串长度建一个对应的一维数组，每一格记录[0-i]区间是否可以被完全拆分，其思路就跟LIS一模一样，外层循环每到一个位置就从头开始一直到i进行一个内部循环检查是否有[j-i]段的字符串在wordDict中可以被找到（这也是这道题一个巧妙的地方，不是拿字典的词一个个去找字符串，而是字符串分一段来字典里面找）下面是代码

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

        for i in xrange(1, n + 1):                                   # 坐标的问题比较tricky，但不是这道题的关键
            for j in xrange(1, i + 1):
                if s[j - 1 : i] in wordDict and res[j - 1]:          # 只要有一个字段在字典里且剩下的部分可被拆分就break
                    res[i] = True
                    break

        return res[n]

上面这种思路实际上是有三个循环的（in关键字实际上就是一个循环），如果将wordDict转为一个哈希表，这里速度变成O(n^2) （不考虑哈希字符串比对的时间）

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        n = len(s)
        dp = [False] * n
        wordList = set(wordDict)

        for i in xrange(n):
            for j in xrange(i + 1):
                if s[j : i + 1] in wordList:
                    dp[i] = dp[j - 1] if j >= 1 else True
                if dp[i]:
                    break

        return dp[n - 1]

当然记忆化搜索也是可行的，这里用了一个memo数组表示从当前下标到字符串终点是否可以被wordDict内的词拆分

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        return self.helper(s, 0, len(s), set(wordDict), [None] * len(s))

    def helper(self, string, start, end, wordDict, memo):
        if start >= end:
            return True

        if memo[start] != None:
            return memo[start]

        for i in xrange(start, end):
            if string[start : i + 1] in wordDict and self.helper(string, i + 1, end, wordDict, memo):
                memo[start] = True
                return memo[start]

        memo[start] = False
        return memo[start]

此题还可以用BFS的方法做，不过也是需要有一个memo来备忘才行

Word Break II

这道题的case太狗，简而言之，使用DFS或者DP的任意一种方法都过不了，因为有一个超长的input，LC的solution里面的解法也只有记忆化搜索一种方法能过（想不通为什么递推的DP不能过而备忘的可以过，不太合常理），如果像解法里这样one pass就过的方法想不出来，其实可以基于word break的那个方法继续做，我们可以把word break里最后的那个矩阵拿出来继续利用，首先这个矩阵记录的就是0 到 i之间的子字符串能否被wordDict里面的词拼凑出来，那我们可以利用这个矩阵继续进行DFS，利用它当一个lookup table，再加上开始的hashset一起就可以得到正确答案，另外因为那个大case的存在，同时也是节省时间的一个很好的方法，我们在dp完成后，可以先检查这个词是不是能被完全break，如果不行我们就不用浪费时间进行DFS而是直接返回空列表就好

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        n = len(s)
        dp = [False] * n
        dp[0] = False
        wordList = set(wordDict)

        for i in xrange(n):
            for j in xrange(i + 1):
                if s[j : i + 1] in wordList:
                    dp[i] = dp[j - 1] if j >= 1 else True
                if dp[i]:
                    break

        if dp[n - 1] == False:
            return []

        result = []
        self.helper(s, 0, len(s), '', result, dp, wordList)
        return result

    def helper(self, string, start, end, tmp, res, ref, checker):
        if start >= end:
            res.append(tmp[1:])
            return 

        for i in xrange(start, end):
            if (start == 0 or ref[start - 1]) and string[start : i + 1] in checker:
                self.helper(string, i + 1, end, tmp + ' ' + string[start : i + 1], res, ref, checker)

此题还有备忘的方法可以不用额外检查one pass AC