最长回文子串

清疚 2022-10-29 12:23 225阅读 0赞

/** * 最长回文子串 * 输入一个字符串s，请找出s中最长回文子串的长度 * dp[i][j]是子串s[i...j]中的最长回文子串的长度 */
    public class Solution11 { 
    
        public static void main(String[] args) { 
            String s = "aaa";
            System.out.println(maxLength(s));
        }
    
        static int maxLength(String s) { 
            int[][] dp = new int[s.length()][s.length()];
            for (int i = 0; i < s.length(); i++) { 
                for (int j = 0; j < s.length(); j++) { 
                    dp[i][j] = 0;
                }
            }
            for (int k = 0; k < s.length(); k++) { 
                dp[k][k] = 1;
            }
            int res = Integer.MIN_VALUE;
            for (int i = s.length()-2; i >= 0; i--) { 
                for (int j = i + 1; j < s.length(); j++) { 
                    if (s.charAt(i) == s.charAt(j)) { 
                        dp[i][j] = dp[i+1][j-1] + 2;
                    }
                    res = Math.max(res, dp[i][j]);
                }
            }
            return res;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关最长回文子串

[题目：给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。][s_ s] > 解题思路：动态规划 > 动态规划的

怼烎@/ 2024年03月08日 04:08/ 0 赞/ 105 阅读

相关 5. 最长回文子串

1、题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： > 输入: “babad” > 输出: “b

╰半夏微凉°/ 2022年12月21日 09:27/ 0 赞/ 216 阅读

相关最长回文子串

最长回文子串 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 赞/ 226 阅读

相关 5. 最长回文子串

> 给你一个字符串 s，找到 s 中最长的回文子串。 > > > > 示例 1： > > 输入：s = "babad" > 输出："bab" > 解释："ab

小鱼儿/ 2022年10月16日 10:00/ 0 赞/ 205 阅读

相关最长回文子串

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

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

相关最长回文子串

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

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

相关 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例 1：输入: "babad" 输出: "bab" 注意

红太狼/ 2022年05月20日 04:10/ 0 赞/ 229 阅读

相关 LeetCode：最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: "babad" 输出: "bab" 注

快来打我*/ 2021年11月22日 15:20/ 0 赞/ 374 阅读

相关最长回文子串

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

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