题解 | #最长回文子串#

最长回文子串

http://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

题目：最长回文子串

描述：对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例1：输入："abc1234321ab",12，返回值：7

解法一：

思路分析：根据题意可得，最长回文子串的概念为找到给定字符串的最大长度连续子串的问题，该字符串就是回文。例如，香蕉的最长回文子串是“anana”。最长回文子串不是唯一的，例如在字符串"abracadabra"中，没有长度大于3的回文子串，但是有两个长度为3的回文子串，即"aca"和"ada"。在某些应用中，可能需要返回所有的最大回文子串，而不是仅仅返回一个子串或返回回文子串的最大长度。

实例分析：输入："abc1234321ab",12

首先定义两个指针变量，i和j，定义最大值maxlen为0，进行以下分析：

输入

I,j

首先判断单个字符a为回文变量，设定maxlen = 1

依次往下判断，此处省略，直接判断结果值

使用判断子串是否为回文函数，最终返回maxlen为7

其具体java代码如下所示：

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int maxLen = 0;
        //暴力解法
        for(int i = 0; i < n; i++){
            for(int j = i+1; j <= n; j++){
                String now = A.substring(i,j);//确定字符
                if(isPalindrome(now) && now.length() > maxLen){
                    maxLen = now.length();//最大长度
                }
            }
        }
        return maxLen;
    }
    //判断子串是不是回文子串
    public boolean isPalindrome(String s){
        int l = s.length();
        for(int i = 0; i < l/2; i++){
            if(s.charAt(i) != s.charAt(l-i-1))//不相等
                return false;
        }
        return true;
    }
}

其时间复杂度为O(N^2)，因为是采用暴力法进行的，设定了两次循环故时间复杂度为O(N^2)，空间复杂度为O(1)。

解法二：

思路分析：可以使用中心扩展法，将给定的字符串的每一个字母当做中心，然后向两边扩展，这样就能找到最长的回文子串，但是需要分情况进行讨论，分为两种具体情况，分别是：

当长度为奇数时，像aba；

当长度为偶数时，像abba；

实例分析：

输入	a	b	c	1	2	3	4	3	2	1	a	b
以a为中心，maxlength = 1
……
以4为中心，maxlength = 7，故返回最终结果为7

具体c++代码如下所示：

class Solution {
public:
    int getLongestPalindrome(string &A, int n) {
        // write code here
        if(n == 0)
            return NULL;
        if(n == 1)
            return 1;
        int maxlength = 0;
        int start;
        for(int i = 0;i < n;i++)//长度为奇数
        {
            int j = i-1,k = i+1;
            while(j >= 0 && k < n && A.at(j) == A.at(k))//循环条件
            {
                if(k - j + 1 > maxlength)
                {
                    maxlength = k - j + 1;
                    start = j;
                }
                j--;
                k++;
            }
        }

        for(int i = 0;i < n;i++)//长度为偶数
        {
            int j = i,k = i + 1;
            while(j >= 0 && k < n && A.at(j) == A.at(k))
            {
                if(k - j + 1 > maxlength)
                {
                    maxlength = k - j + 1;
                    start = j;
                }
                j--;
                k++;
            }
        }
        if(maxlength > 0)
            return maxlength;
        return NULL;
        }
};

其时间复杂度同上，均为O(N^2)，时间复杂度为O(1)。

算法自然分析文章被收录于专栏

在解决问题的同时，不断与人交流学习，通过牛客各式各样的题目，学习分享。