[Leetcode 5] 最长回文子串Longest Palindromic Substring
2021/11/28 6:39:51
本文主要是介绍[Leetcode 5] 最长回文子串Longest Palindromic Substring,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题
求最长回文子串,即左右对称
Given a string s
, return the longest palindromic substring in s
.
Example 1:
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd" Output: "bb"
Example 3:
Input: s = "a" Output: "a"
Example 4:
Input: s = "ac" Output: "a"
思路
俩种情况,ab ba和ab b ba
回文串,经典的DP,第[i][j]是否为回文,由[i+1][j-1]&&本身决定(除了*)
*tips: 对角线恒为true,i-j<2时,是否为回文,只由s.i是否等于s.j决定(图中三角形)
代码
*注意循环顺序,因为上下三角本质是一样的,为了更快,只用选其中一个三角
*选了三角后要注意扫的方向,从前往后可能[i+1][j-1]还没被赋值
public static String longestPalindrome(String s) { int n = s.length(); String res = null; boolean[][] dp = new boolean[n][n]; for (int i = n - 1; i >= 0; i--) { for (int j = i; j <n; j++) { dp[i][j] = s.charAt(i) == s.charAt(j) && ((j-i)<2||dp[i + 1][j - 1]); if (dp[i][j] && (res==null|| j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; }
这篇关于[Leetcode 5] 最长回文子串Longest Palindromic Substring的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享