`

最长回文子串

 
阅读更多

 

 

      思路:

      分两种情况考虑:

      第一种:奇数回文,比如:“aba”

      第二种:偶树回文 ,比如:“adda”

      然后遍历字符串,以该字符为中心,检查它的前后能够构成上述两种情况中的

      回文串。

      时间复杂度: O(n ^2)

 

      代码: 

public class Solution {
    //最长回文子串
    public String longestPalindrome(String s) {
        int len =  s.length();
        if(len == 1) return s;
        int maxLen = 0;
        String ps ="";
        for(int i = 1 ; i < len ; i++) {
           int low = i - 1;
           int high  = i + 1;
        //   奇数回文 以s[i]为中心.. 查看它的左右两边是否满足回文
           int count = 0;           
           while(low >= 0 && high < len && s.charAt(low) == s.charAt(high)) {
               count = high - low + 1;
               low--;
               high++;
           }
           if(count > maxLen) {
                   ps = s.substring(i - count/2 , i + count/2 + 1);
                   maxLen = count;
            }
//检查完奇数后,立马检查是否满足偶数 其实如果满足的话,一定该回文串所有字符相等
        //   偶数回文
           count = 0;
           low = i - 1;
           high = i;
           while(low >= 0 && high < len && s.charAt(low) == s.charAt(high)) {
               count = high - low + 1;
               low--;
               high++;
           } 
           if(count > maxLen) {
                   ps = s.substring(i - count/2 , i + count/2);
                   maxLen = count;
           }
        }
        return ps;
    }

}

 

 

   动态规划求解:

    思路:

    对于字符串"aXa" , 如果子串X为回文串,那么aXa就是回文串 

    X不是回文串,那么"aXa"也一定不是回文串

    所以,可以用一个状态转移方程,来存放子串是否为回文;

   matrix[i][j]的意思就是 字符串中i到j是否为回文串

   注意这里 i >= j的,也就是说,最后的结果矩阵只有一半。

   

   状态转移方程:

   matrix[i][j] = 1 // i = j

   matrix[i][j] = s[i] == s[j]     // i = j - 1   i j 相邻 只要两者相等即可

   matrix[i][j] = s[i]==s[j] && matrix[i + 1][ j - 1] // 其他情况

  

   

   观察这个递归式,可知,matrix[i][j] 要利用到matrix[i + 1][j - 1]

   所以,这次不能一行一行的求出值,而应当一列一列的求值。

 

   代码:

 

  public static String longestPalindrome(String s) {
         int len = s.length();
         boolean[][] matrix = new boolean[len][len];
         int maxLen = 1;
         int start = 0;
        //初始化  
         for(int i = 0; i < len ; i++) {
             matrix[i][i] = true;
         }
         
         for(int col = 1 ; col < len ; col++) {
             for(int row = col - 1; row >= 0 ; row--) {
                 if(s.charAt(col) == s.charAt(row)) {
//row col 不相邻 但是 子串不回文
                    if(row + 1 < col - 1 && !matrix[row + 1][col - 1]) {
                	 matrix[row][col] = false;
                         continue;
                    }
                     matrix[row][col] = true;
                     int length = col - row + 1;
                     if(length > maxLen) {
                         maxLen = length;
                         start = row;
                     }
                 }         
             }
         }
         return s.substring(start,start+maxLen);
    }

 

     

      

分享到:
评论

相关推荐

    最长回文子串.cpp

    最长回文子串

    C++/C求最长回文子串

    输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...

    数据结构问题:“最长回文子串问题”(Longest Palindromic Substring),详细解法和代码实现

    数据结构问题:“最长回文子串问题”(Longest Palindromic Substring),详细解法和代码实现; 数据结构问题:“最长回文子串问题”(Longest Palindromic Substring),详细解法和代码实现; 数据结构问题:“最长...

    双回文子串的相关解法

    - **最长回文子串预处理**:预处理以每个位置为中心的最长回文子串。 - **结构体数组**:构造一个结构体数组存储每个回文子串的左边界和中心位置,并按左边界排序。 - **动态维护Set**:枚举中心位置p,动态维护一个...

    如何输出字符串的最长回文子串

    在编程领域,字符串处理是常见的任务之一,而寻找字符串中的最长回文子串是一个经典问题。回文子串是指在不改变子串中字符顺序的情况下,读取子串正向和反向是一样的字符串。例如,“madam”、“racecar”等都是回文...

    最长回文子串(dp)1

    1. 动态规划(DP)算法在解决最长回文子串问题中的应用 在解决最长回文子串问题时,动态规划(DP)算法是一个非常有效的方法。动态规划算法可以将问题分解成多个小问题,然后将这些小问题的解组合成最终的解。 在...

    最长回文子串Manacher算法1

    Manacher's Algorithm是一种用于在O(n)时间复杂度内找到字符串中最长回文子串的高效算法。这个算法的核心思想是通过巧妙地预处理字符串并利用回文串的对称性来减少重复计算,从而达到线性时间复杂度。 首先,我们...

    C语言-C语言编程基础之leetcode题解第5题最长回文子串.zip

    在本压缩包中,主题聚焦于C语言编程基础与LeetCode算法题目的解法,特别是针对第五题“最长回文子串”的问题。这是一道经典的字符串处理问题,旨在锻炼和提升C语言程序员的逻辑思维和算法实现能力。在本文中,我们将...

    c++-c++编程基础之leetcode题解第5题最长回文子串.zip

    第5题“最长回文子串”是LeetCode中的一个经典问题,它涉及到字符串处理和动态规划等核心编程概念。在这个题解中,我们将深入探讨如何用C++解决这个问题。 首先,我们要理解什么是回文子串。一个回文串是正读反读都...

    字符串处理- 回文串相关- 求最长回文子串.rar

    本资料“字符串处理- 回文串相关- 求最长回文子串.rar”主要探讨的是如何在给定的字符串中找到最长的回文子串。 回文子串是字符串的一个子序列,它本身是一个回文串。例如,字符串 "babad" 的回文子串有 "bab", ...

    Manacher's ALGORITHM_ O(n)时间求字符串的最长回文子串 - Blog of Felix021 - Tec

    Manacher's 算法是一种高效解决字符串中最长回文子串问题的算法,它能在O(n)的时间复杂度内完成,其中n是字符串的长度。这个算法由Manacher在1975年提出,主要利用了回文串的对称性质来减少不必要的重复计算。 首先...

    java面试-leetcode面试java编程题解之第5题最长回文子串-java题解.zip

    其中,第5题“最长回文子串”是经典的字符串处理问题,对于Java程序员来说,理解和解决这个问题至关重要。下面将详细探讨这个题目以及相关的Java编程知识点。 **题目描述:** 给定一个字符串`s`,找到`s`中的最长...

    最长回文子串c语言

    自己编的,望大家指点!这是西工大期末考试的题目,做了好久才做出来

    查找一个字符串中的最长回文子串,这里采用的是Manacher算法

    查找一个字符串中的最长回文子串,这里采用的是Manacher算法 比如:cababcaac的最长回文子串就是caac 其中的aba bab也都是回文子串 (Manacher算法) 效率很高的一种查找算法,效率可以达到O(2n+1)

    leetcode最长回文子串.md

    leetcode刷题宝典

    python实现求最长回文子串长度

    在Python编程中,解决“最长回文子串”问题是一个经典的字符串处理问题。回文串是指正读和反读都一样的字符串,例如“madam”和“level”。本篇文章将详细探讨如何用Python高效地找到给定字符串的最长回文子串的长度...

    4.2.3 使用Manacher算法求最长回文子串.pdf

    ### 使用Manacher算法求最长回文子串 #### 概述 在计算机科学领域,寻找一个给定字符串中的最长回文子串是一个经典的算法问题。回文是指一个字符串正读和反读都一样的序列,例如“abcba”。解决这个问题的传统方法...

    最长回文子串.md

    最长回文子串.md

Global site tag (gtag.js) - Google Analytics