Leetcode_005_最长回文串(高频题)
2021/5/2 18:27:05
本文主要是介绍Leetcode_005_最长回文串(高频题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给你一个字符串 s,找到 s 中最长的回文子串。leetcode链接
解题思路
方法1
第一种就是遍历每个位置,从当前位置开始向两边检查最大回文串
这个方法需要注意的是:由于回文串的长度可能为奇数或者偶数,所以检查的时候,要考虑两种情况;
- 如果为奇数,当前位置就是中心位置,从两边开始检查,
find(i, i)
- 如果为偶数,当前位置只是左边中心,要从当前位置
i
和下一个位置i+1
开始检查,find(i, i+1)
代码
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() <= 0) return s; int maxLen = 0; int start = 0; for (int i = 0; i < s.length(); i++) { int len1 = find(s.toCharArray(), i, i); // 长度为奇数 int len2 = find(s.toCharArray(), i, i + 1); // 长度为偶数 int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; // 0 1 2 i = 1, len = 3, start = 1 - (2/2) = 0 // 0 1 2 3 i = 1, len = 4, start = 1 - (3/2) = 0 start = i - (len - 1) / 2; } } // substring(a,b) 是左闭右开 return s.substring(start, start + maxLen); } // 从当前位置寻找最长回文串 private int find(char[] cs, int left, int right) { int len = cs.length; while (left >= 0 && right < len && cs[left] == cs[right]) { left--; right++; } return right - left - 1; } }
方法2
- 这个方法用到了动态规划的思想。本题可以使用暴力解法:每遍历到一个位置
i
,就在区间\([0, i]\)内两边往中间逼近,得到当前区间内的最大回文串。 - 动态规划就是用来优化上述暴力解法,使用 \(dp[i][j]\) 记录边界为
i
和j
时是否为回文串,如果是,那只要 \(cs[i - 1] == cs[j + 1]\),那么因为内层为回文串且左右边界字符相等 - 因此新的区间 \([i-1, j+1]\) 就构成了更长的回文串
代码
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } char[] cs = s.toCharArray(); int maxLen = 1; int start = 0; boolean[][] dp = new boolean[cs.length][cs.length]; for (int j = 0; j < cs.length; j++) { for (int i = 0; i < j; i++) { // 三个字符以内,或者内部为回文串 if (cs[i] == cs[j] && (j - i <= 2 || dp[i+1][j-1])) { dp[i][j] = true; if (j - i + 1 > maxLen) { maxLen = j - i + 1; start = i; } } } } return s.substring(start, start + maxLen); } }
这篇关于Leetcode_005_最长回文串(高频题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望