• 售前

  • 售后

热门帖子
入门百科

字符串的最长回文,从最长回文巨细到最长回文是谁?

[复制链接]
石头剪子布854 显示全部楼层 发表于 2022-1-16 10:31:16 |阅读模式 打印 上一主题 下一主题
字符串的最长回文



媒介

   通过动态规划来获取字符串的最长回文长度以及巨细。
  一、标题与示例

1、标题

   给定一个字符串,求其最长回文。
  2、示例

   1-雾锁山头山锁雾
2-天连水尾水连天
    示例 1:
输入:s = “babad”
输出:“bab”
表明:“aba” 同样是符合题意的答案。
    示例 2:
输入:s = “cbbd”
输出:“bb”
    示例 3:
输入:s = “a”
输出:“a”
    示例 4:
输入:s = “ac”
输出:“a”
  二、题解

1、求长度(DP)

  1. public int longestPalindrome(StringBuilder s) {
  2.         int len = s.length();
  3.         int[][] dp = new int[len][len];
  4.         for (int i = 0; i < len; i++) {
  5.             dp[i][i] = 1;
  6.         }
  7.         for (int i = 1; i < len; i++) {
  8.             for (int j = i - 1; j >= 0; j--) {
  9.                 if (s.charAt(i) == s.charAt(j) && dp[i - 1][j + 1] == i - j - 1) {
  10.                     dp[i][j] = dp[i - 1][j + 1] + 2;
  11.                     continue;
  12.                 }
  13.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j + 1]);
  14.             }
  15.         }
  16.         return dp[len - 1][0];
  17.     }
复制代码
2、求回文

  1. public String longestPalindrome(String s) {
  2.         int len = s.length();
  3.         int[][] dp = new int[len][len];
  4.         int first = 0, end = 0;
  5.         for (int i = 0; i < len; i++) {
  6.             dp[i][i] = 1;
  7.         }
  8.         for (int i = 1; i < len; i++) {
  9.             for (int j = i - 1; j >= 0; j--) {
  10.                 if (s.charAt(i) == s.charAt(j) && dp[i - 1][j + 1] == i - j - 1) {
  11.                     dp[i][j] = dp[i - 1][j + 1] + 2;
  12.                     if (end - first < i - j) {
  13.                         first = j;
  14.                         end = i;
  15.                     }
  16.                     continue;
  17.                 }
  18.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j + 1]);
  19.             }
  20.         }
  21.         return s.substring(first, end + 1);
  22.     }
复制代码
参考文献

[1] LeetCode 原题

免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作