Leetcode#5. Longest Palindromic Substring（最长回文子串：二种解法），

Leetcode#5. Longest Palindromic Substring（最长回文子串：二种解法），

声明：题目解法使用c++和Python两种，重点侧重在于解题思路和如何将c++代码转换为python代码。
本题c++采用两种方法解答，python用到了闭包的知识。

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example:

Input: “cbbd”

Output: “bb”

题意

给你一个字符串s,求出s中的最长回文子串输出。
首先你要知道什么是回文？
一个字符串从左向右读和从右向左读一样。
例如aba。

思路一：枚举

直接枚举所有的子串，判断是否回文。
- 时间复杂度为：O（n^3）
QAQ果断超时。

class Solution {
public:
    int Palindrome(string s)
    {
        for(int i=0; i<s.size(); i++)
            if(s[i] != s[s.size()-1-i])
                return 0;
        return 1;
    }
    string longestPalindrome(string s) 
    {

        string temp = "",res;
        int i,j,k,ms = 0;
        for(i=0; i<s.size(); i++)
        {   temp = "";
            for(j=i; j<s.size(); j++)
            {
                temp += s[j];
                if(Palindrome(temp)==1)
                {
                    if(ms<temp.size())
                    {
                        ms = temp.size();
                        res = temp;
                    }
                }
            }
        }
        return res; 
    }
};

思路二：对称枚举

从字符串的某一位置，作为对称中心位置，向两侧扫描检测最长回文长度 。

• 时间复杂为0（n*n）

class Solution {
public:
    string ss;
    int dfs(int left, int right)
    {
        if(left<0 || right >=ss.size() ||ss[left] !=ss[right])
            return left+1;
        else
            //一定要有返回的出口，前方高能，卡了我一下午
            return dfs(left-1,right+1);        
    }
    string longestPalindrome(string s) 
    {
        ss = s;
        string res="";
        int i,ms = 0,now_left,len,sx=0;

        for(i = 0; i + 1 <s.size(); i ++ )
        {   
            if(s[i]==s[i+1]) //偶数
            {  
                now_left = dfs(i,i+1);
                len = (i-now_left+1)*2;

                if(ms<len)
                {
                    ms = len;
                    sx = now_left;
                }
            }
            if(i-1>=0&&s[i-1]==s[i+1])//奇数
            {
                now_left = dfs(i-1,i+1);
                len = (i-now_left)*2+1;

                if(ms<len)
                {
                    ms = len;
                    sx = now_left;
                }
            }
        }

        //找不到回文字符串，返回第一个数
        if(ms==0)
            res+=s[0];

        for(i=sx; i<sx+ms;i++)
            res+=s[i];
        return res; 
    }
};

Python代码

这里用到了python高阶函数中的闭包：
内层定义一个判断回文的函数调用外层还是中的s变量，称之为闭包。内层函数无法被外部访问。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        #使用外部函数的局部参数
        def dfs(left, right):
            if left < 0 or right >= len(s) or s[left] != s[right]:
                return (left + 1)
            else:
                return dfs(left-1, right+1)
        ms = 0
        now_left = 0
        sx = 0
        for i in range(0,len(s)-1):
            if s[i] == s[i+1]:
                now_left = dfs(i, i+1)
                now_len = (i-now_left+1)*2
                if ms<now_len:
                    ms = now_len
                    sx = now_left
            if i-1>=0 and s[i-1] == s[i+1]:
                now_left = dfs(i-1, i+1)
                now_len = (i-now_left)*2+1
                if ms<now_len:
                    ms = now_len
                    sx = now_left

        res = ""
        if ms == 0:
            res+=s[0]
        for i in range(sx,sx+ms):
            res+=s[i]
        return res

前方高能

在写程序的时候犯了一个低级的错误：
是这样的

 int dfs(int left, int right)
    {
        if(left<0 || right >=ss.size() ||ss[left] !=ss[right])
            return left+1;
        else
            //错误点
            dfs(left-1,right+1);        
    }

没有返回，这样导致的错误是在多次调用dfs导致函数没有返回值或者直接得到一个系统随意分配的值。
最后贴一个九章算术里面的思路相同的一个写法，用#填充字符串，不用考虑奇偶性。

class Solution {

public:

    string longestPalindrome(string s) {

        string str = "", ans = "";

        int len = s.length();

        int maxl = -1, cnt;

        for (int i = 0; i < len; i++) {

            str += '#';

            str += s[i];

        }

        str += '#';

        // 将原字符串扩展成#a#b#的形式可以直接枚举长度，不用考虑回文串长度的奇偶性

        for (int i = 1; i < 2 * len; i++) {

            cnt = 0;

            while ((i - cnt >= 0) && (i + cnt <= 2 * len) && (str[i - cnt] == str[i + cnt]))

                cnt++;

            cnt--;

            if (cnt > maxl) {

                maxl = cnt;

                ans = s.substr((i - cnt) / 2, (i + cnt) / 2 - (i - cnt) / 2);

            }

        }

        return ans;

    }

};

GitHub本题题解：https://github.com/xuna123/LeetCode/blob/master/Leetcode%235.%20Longest%20Palindromic%20Substring.md