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

代码随想录算法训练营第五十九天 | 647. 回文子串 516.最长回文子序列

1. 回文子串 

647. 回文子串 - 力扣(LeetCode)

一个子串左右两个元素相等,并且中间对称,才是回文子串

即 i=j 时,[i+1: j-1]对称

dp[i][j]: [i:j] 是否是回文字串

当 子串长度大于2 由 dp[i+1][j-1] 推出, i 由 i+1推出 所以 i 要倒序

不大于2时,则由 i j 决定

class Solution {public int countSubstrings(String s) {int length = s.length();boolean dp[][] = new boolean[length][length];// dp[i][j] [i:j] 是否是回文字串int res = 0;for(int i = length-1; i > -1; i--){for(int j = i; j < length; j++){if(s.charAt(i) == s.charAt(j)){if(j-i <= 1){ // 字串长度不超过2dp[i][j] = true;res++;}else if(dp[i+1][j-1]){dp[i][j] = true;res++;}}}}return res;}
}

 

2. 最长回文子序列

516. 最长回文子序列 - 力扣(LeetCode)

子序列可以不连续 所以当 s[i] != s[j] 也需要考虑

s[i] == s[j] 时,中间的长度 + 2

s[i] != s[j] 时,要考虑左右两个哪个加入中间后更长

class Solution {public int longestPalindromeSubseq(String s) {int length = s.length();int[][] dp = new int[length][length];for(int i = length-1; i > -1; i--){dp[i][i] = 1; // 字串长度为 1 必然相等for(int j = i + 1; j < length; j++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i+1][j-1] + 2; // dp[1][2] = dp[2][1] + 2 = 0 + 2}else{dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][length-1];}
}

http://www.lryc.cn/news/183324.html

相关文章:

  • React Redux
  • StreamingLLM - 处理无限长度的输入
  • [Linux 命令] nm 详解
  • 好文学作品的鉴赏标准
  • 智慧公厕:将科技融入日常生活的创新之举
  • ROS(0)命令及学习资源汇总
  • NodeMCU ESP8266开发流程详解(图文并茂)
  • 【最终版】tkinter+matplotlib实现一个强大的绘图系统
  • Postman使用实例
  • 【ES的优势和原理及分布式开发的好处与坏处】
  • Autosar诊断实战系列23-CanTp半/全双工及相关工程问题思考
  • 【Pandas】数据分组groupby
  • 【图像处理GIU】图像分割(Matlab代码实现)
  • Java中的锁与锁优化技术
  • 布局与打包
  • UVa11324 - The Largest Clique
  • 【Linux】TCP的服务端(守护进程) + 客户端
  • 1.7. 找出数组的第 K 大和原理及C++实现
  • 基于微信小程序的付费自习室
  • 纪念在CSDN的2048天
  • 云原生Kubernetes:简化K8S应用部署工具Helm
  • qml保姆级教程五:视图组件
  • 2310d编译不过
  • CleanMyMac X4.14.1最新版本下载
  • 芯驰D9评测(3)--建立开发环境
  • 阿里云服务器IP地址查询方法(公网IP和私网IP)
  • 第47节——使用bindActionCreators封装actions模块
  • QT、c/c++通过宏自动判断平台
  • 对比表:阿里云轻量应用服务器和服务器性能差异
  • 中国1km分辨率月最低温和最高温度数据集(1901-2020)