时间戳

首页 > 解决方案 > 分词的时间复杂度分析

python - 分词的时间复杂度分析

问题描述

以下代码的时间复杂度分析和空间复杂度分析是什么：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s or not dict:
            False

        N=len(s)
        ans=[False for i in range (N+1)]
        ans[0]=True


        for index in range(N):
            if ans[index]:
                for word in wordDict:
                    L=len(word)
                    if index+L <= N and s[index:index+L]==word:
                        ans[index+L]=True

        return ans[-1]

给定一个非空字符串s和一个wordDict包含非空单词列表的字典，确定是否s可以分割成一个或多个字典单词的空格分隔序列。

标签： pythontime-complexitybig-o

解决方案

该解决方案的时间复杂度为O(n*m*k)- 其中：

  • n是字符串的长度s。
  • m是 中的单词数wordDict。
  • k是 中单词的平均长度wordDict。

解释，您重复n次数，每次检查wordDict（m总计）中的每个单词，并且对于每个这样的重复，您阅读整个单词（长度k）。

空间复杂度是O(n)- 您的 aux 数组独立于单词的数量wordDict或它们的长度，并且没有额外的空间分配1取决于字典。

(1) 好吧，我不确定 python 是如何实现的s[index:index+L]，但无论哪种方式，这都不会被 倍数n，并且一次不会分配超过一次，也不会分配 if L > n- 所以它不会影响空间复杂度。

推荐阅读