139/140. Word Break I/II

  • 139题
    使用动态规划
    要判断leetcode能不能在字典中找到:令sub="e",判断"leetcod"是否为True/
    令sub="de",判断"leetco"是否为True,不断循环,直到判断"leetcode"整体是否在字典中,只要有一次判断成功则直接break当前判断,也就是leetcode能找到。下一次判断leetcodex(更长的string)是否能找到。
    res长度为len(s) + 1,初始化令res[0] = True.
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        res = [False] * (len(s) + 1)
        res[0] = True
        for i in range(1, len(s) + 1):
            cur = s[:i]
            for length in range(1, i + 1):
                sub = cur[-length:]
                remain_length = i - length
                if sub in wordDict:
                    if res[remain_length]:
                        res[i] = True
                        break
        return res[len(s)]
  • 140题,使用递归。这种要返回所有可能结果的题目,无法用动态规划解。
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        # 转为set(hashtable),效率更高
        wordDict = set(wordDict)
        return self.wordBreakHelper(s, wordDict, {})
    
    def wordBreakHelper(self, s, wordDict, memory):
        if s == '':
            return ['']
        # 如果memory中有结果,直接从memory中取值
        if s in memory.keys():
            return memory[s]
        res = []
        # s由前一部分sub和后一部分remain(数组)构成, 如果sub在字典中进行下一步骤
        # 如果remain为[''](当s为''的返回值),temp_res由sub构成
        # 如果remain不为空,temp_res由 sub + " " + remain中的元素 构成
        # 当remian为空,也会调用for循环,不过remain内没有元素,直接pass
        for i in range(1, len(s) + 1):
            sub = s[:i]
            if sub in wordDict:
                remain = self.wordBreakHelper(s[i:], wordDict, memory)
                if remain == ['']:
                    res.append(sub)
                else:
                    # 如果remain为空进入到else内,但是不会进入循环
                    for item in remain:
                        res.append(sub + " " + item)
        # 将结果加入到memory中,key为s
        memory[s] = res
        return res
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容