求最长回文串

向右看齐 2022-10-10 01:37 147阅读 0赞

## 一、题目 ##

给定一个字符串 s，找到 s 中最长的回文子串

## 二、动态规划解法 ##

public String longestPalindrome(String s){ 
            int len  = s.length();
            if(len < 2){ 
                return s;
            }
    
            int maxLen = 1;
            int begin = 0;
            //dp[i][j] 表示 s[i...j]是否是回文串
            boolean[][] dp = new boolean[len][len];
            //初始化：所有长度为 1 的子串都是回文串
            for(int i = 0; i < len; i++){ 
                dp[i][i] = true;
            }
    
            char[] charArray = s.toCharArray();
            //递推开始
            //先枚举子串长度
            for (int L = 2; L < len; L++) { 
                //枚举左边界，左边界的上线设置可以宽松一点
                for(int i = 0;i < len; i++){ 
                    //由 L和 i 可以确定右边界，即 j - i + 1 = L
                    int j = L + i -1;
                    //如果右边界越界，就可以退出当前循环
                    if(j >= len){ 
                        break;
                    }
    
                    if(charArray[i] != charArray[j]){ 
                        dp[i][j] = false;
                    }else { 
                        if(j-i<3){ 
                            dp[i][j] = true;
                        }else { 
                            dp[i][j] = dp[i+1][j-1];
                        }
                    }
    
                    //只要 dp[i][L] == true 成立，就表示子串 s[i...L]是回文，此时记录回文长度和起始位置
                    if(dp[i][j] && j -i + 1 > maxLen){ 
                        maxLen = j -i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关题目：求最长回文串并求出回文串

动态规划 ![64cf9cbd849d41a59cdcb89fa7741a97.png][] include<bits/stdc++.h> using

曾经终败给现在/ 2024年03月26日 23:42/ 0 赞/ 58 阅读

相关最长回文子串

最长回文子串 1、参考资料 https://leetcode-cn.com/problems/longest-palindromic-substring/ htt

╰半夏微凉°/ 2022年12月08日 05:24/ 0 赞/ 228 阅读

相关最长回文子串

/ 最长回文子串输入一个字符串s，请找出s中最长回文子串的长度 dp[i][j]是子串s[i...j]中的最长回文子串的长度 / public clas

清疚/ 2022年10月29日 12:23/ 0 赞/ 225 阅读

相关求最长回文串

一、题目给定一个字符串 s，找到 s 中最长的回文子串二、动态规划解法 public String longestPalindrome(String

向右看齐/ 2022年10月10日 01:37/ 0 赞/ 148 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 259 阅读

相关最长回文子串

回文串指给定的字符串，正着读和反着读都是一样的。如ADA，反过来还是ADA即为回文串。最长回文子串指查找一给定字符串中最长的回文串。通常有以下4种解法。主要考虑的是时间复杂

雨点打透心脏的1/2处/ 2022年08月07日 04:43/ 0 赞/ 265 阅读

相关最长回文子串

include <iostream> include <vector> include <string> include <algori

淩亂°似流年/ 2022年06月17日 06:53/ 0 赞/ 293 阅读

相关最长回文串

public String longestPalindrome(String s) { int start = 0, end = 0;

刺骨的言语ヽ痛彻心扉/ 2022年06月10日 10:22/ 0 赞/ 183 阅读

相关 python 最长回文串

from collections import Counter class Solution : """ @param s: a

Love The Way You Lie/ 2022年05月21日 02:52/ 0 赞/ 208 阅读

相关最长回文子串

【题目】给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。输入: “babad” 输出: “bab” 注意: “aba”

骑猪看日落/ 2021年09月21日 05:28/ 0 赞/ 386 阅读