leetcode---139.单词拆分

大佬教程收集整理的这篇文章主要介绍了leetcode---139.单词拆分，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

@H_673_0@题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

@H_673_0@示例

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

@H_673_0@解题思路

我们定义 (dp[j]) 表示字符串 (s) 中 (i) 个字符组成的字符串 (s[i,...,j]) 是否在字典中出现。用，(dp[i])其前面字符组成的字符串(s[0,...,i-1]) 是否能够被空格拆分成若干个字典中出现的单词。因此我们可以得出如下状态转移方程：

其中(check(s[i,...,j]))表示该子串出现在字典中。 对于边界条件，我们定义(dp[0]=TruE)表示空串且合法。

@H_673_0@代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [false]*(n+1)
        dp[0]=True

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

        return dp[-1]

@H_673_0@复杂度

• 时间复杂度为 (O(n^2))；
• 空间复杂度为 (O(n))。

大佬总结

以上是大佬教程为你收集整理的leetcode---139.单词拆分全部内容，希望文章能够帮你解决leetcode---139.单词拆分所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。