问题描述

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

问题分析

一开始想wordDict建成树状来进行搜索匹配，但是这么做超时，主要原因是有很多分支导致很多并列的递归调用。
参考了九章算法，主要思路就是记录可以到达的位置，然后从这种可以到达的位置再得到通过一个单词可以到达的位置。

AC代码

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        n = len(s)
        if len(wordDict) == 0:
            return n == 0
        flag = [False for i in range(n+1)]
        flag[0] = True
        maxLen = max([len(word) for word in wordDict])

        for i in range(1, n+1):
            if not flag[i-1]:
                continue
            for j in range(1, min(n, i+maxLen) + 1):
                if s[i-1:j] in wordDict:
                    flag[j] = True
        return flag[n]

Runtime: 56 ms, which beats 70.62% of Python submissions.