Daily LeetCode 139. Word Break

https://leetcode.com/problems/word-break/

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:

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

Example 2:

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:

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

思路及代码：

这一题是要看给定的字符串经过拆分，是否能够完全匹配字典中的词汇，即s由wordDict中的词构成。我们通过一个二重循环，模拟划分的过程。初始化一个dp数组，将dp[0]设置为1，在遍历过程中更新dp数组。dp[i]等于1的条件有两个：一是dp[j]等于1，表示s[0:j]已经成功划分；二是s[j:i]属于wordDict，表示s[j:i]可以成功划分。最终，我们只需要看dp数组的最后一位是否为1即可。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        for i in range(len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = 1
                    break

        return dp[-1] == 1