問(wèn)題描述

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

問(wèn)題分析

一開(kāi)始想wordDict建成樹(shù)狀來(lái)進(jìn)行搜索匹配，但是這么做超時(shí)，主要原因是有很多分支導(dǎo)致很多并列的遞歸調(diào)用。
參考了九章算法，主要思路就是記錄可以到達(dá)的位置，然后從這種可以到達(dá)的位置再得到通過(guò)一個(gè)單詞可以到達(dá)的位置。

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.