卖萌的弱渣

I am stupid, I am hungry.

Binary Tree Zigzag Level Order Traversal

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

Solution

假设dp(i)表示长度为i的字串能否别切分，dp方程如下:

dp(i) = dp(j) && s[j, i) in dict

(Word-Break.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """

        if not wordDict:
            return len(s)==0

        n = len(s)
        dp = [False]*(n+1)

        dp[0] = True

        for i in range(1,n+1):
            for j in range(i-1,-1,-1):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
        return dp[n]