首页 > itarticle > 139. word break 解法

139. word break 解法

admin 11月 12, 2020 0

139. Word Break

Difficulty: Medium

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

1
2
3
 
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1
2
3
4
 
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
 
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

解法

法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 

class :
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wd = set(wordDict)
        # if s in wd:
        #     return True
        dp = [False for _ in range(len(s) + 1)]
        dp[0] = True
        for j in range(len(s)):
            for i in range(j+1):
                if s[i:j+1] in wd:
                    dp[j + 1] |= dp[i]
        # print(dp)
        return dp[len(s)]

法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
# 简洁优雅的解法
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        dp = [False] * (len(s) + 1) # dp[i] means s[:i+1] can be segmented into words in the wordDicts 
        dp[0] = True
        for i in range(len(s)):
            if dp[i]:
                for j in range(i, len(s)):
                    if s[i: j+1] in wordDict:
                            dp[j+1] = True
                    
        return dp[-1]
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能