当前位置: 首页 > article >正文

Leetcode 刷题笔记1 动态规划part13

leetcode  647 回文子串

暴力解法:

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        for i in range(1, len(s) + 1):
            for j in range(len(s) - i + 1):
                if s[j:j + i] == s[j:j + i][::-1]:
                    ans +=1
        return ans

dp:

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        ans = 0
        for i in range(len(s)-1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    ans += 1
        return ans

中心扩散法(双指针法):

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        for i in range(len(s)):
            ans += self.extend(s, i, i,len(s))
            ans += self.extend(s, i, i+1,len(s))
        return ans
    def extend(self, s, i, j, n):
        ans = 0
        while i >= 0 and j < n and s[i] == s[j]:
            i -= 1
            j += 1
            ans += 1
        return ans

leetcode 516 最长回文子串

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0] * len(s) for i in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s)-1, -1, -1):
            for j in range(i + 1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][-1]


 

原文地址:https://blog.csdn.net/pinglejun/article/details/146251933
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586040.html

相关文章:

  • SWPU 2022 新生赛
  • leetcode 102. 二叉树的层序遍历
  • 机器学习神经网络中的损失函数表达的是什么意思
  • 让网站变得更智能!架构标记如何提升SEO并吸引更多流量?
  • CentOS7 服务器安装 Hadoop 和 Hive
  • xlua 运行原理
  • 编程自学指南:java程序设计开发,数组与集合,为什么需要数组和集合?数组的声明与初始化, 数组遍历,多维数组
  • redis工具类
  • 【前端拓展】Canvas性能革命!WebGPU + WebAssembly混合渲染方案深度解析
  • FastAPI复杂查询终极指南:告别if-else的现代化过滤架构
  • 分享vue好用的pdf 工具实测
  • 【redis】发布订阅
  • windows11 的 .gitignore 文件失效(从来没有进行 commit 以及 add 操作,只是 git init 了)
  • 科技快讯 | “垃圾短信”可以被识别了;阿里正式推出AI旗舰应用;OpenAI深夜发布全新Agent工具
  • GC 频率和触发条件
  • 31、map deque list的实现原理【中高频】
  • AdaLoRA 参数 配置:CAUSAL_LM“ 表示因果语言模型任务
  • 【数据库】10分钟学会MySQL的增删改查:数据库、表、表记录操作指南
  • 分布式IO模块:架起城轨交通物理层与控制层的信息桥梁
  • WHQL微软驱动签名认证,让企业驱动在Windows系统畅通无阻