5最长回文子串

喜欢ヅ旅行 2023-02-28 15:24 18阅读 0赞

## 一、前言 ##

标签：动态规划、中心扩散。

问题来源LeetCode 5 难度：中等。

问题链接：[https://leetcode-cn.com/problems/longest-palindromic-substring/][https_leetcode-cn.com_problems_longest-palindromic-substring]

## 二、题目 ##

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

**示例1：**

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

**示例2：**

输入: "cbbd"
    输出: "bb"

## 三、思路 ##

两种解题方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

**复杂度分析**：时间复杂度 O(n2)，空间复杂度O(n2)

**方法二：中心扩散**

中心点可能是一个也可能是两个，以中心点向两边扩散判断最长的回文串。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 005_LongestPalindrome.h
    * @label   : 动态规划、中心扩散
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107497550
    * @author  : niebingyu
    * @date    : 2020/07/20
    * @title   : 5.最长回文子串
    * @purpose : 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    *
    *
    * 示例1：
    * 输入: "babad"
    * 输出: "bab"
    * 注意: "aba" 也是一个有效答案。
    *
    * 示例 2：
    * 输入: "cbbd"
    * 输出: "bb"
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_LONGESTPALINDROME namespace NAME_LONGESTPALINDROME {
    #define NAMESPACE_LONGESTPALINDROMEEND }
    NAMESPACE_LONGESTPALINDROME
    
    // 方法一，动态规划
    // f(i, i) = true
    // f(i,j) = f(i+1, j−1) ∧ (Si == Sj)
    // 时间复杂度 O(n2), 空间复杂度O(n2)
    class Solution_1 
    {
    public:
        string longestPalindrome(string s) 
        {
            int n = s.size();
            vector<vector<int>> dp(n, vector<int>(n));
            string ans;
            for (int j = 0; j < n; ++j) 
            {
                for (int i = j; i >= 0; --i) 
                {
                    if (i == j) 
                        dp[i][j] = 1;
                    else if (j - i == 1) 
                        dp[i][j] = (s[i] == s[j]);
                    else 
                        dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
                        
                    if (dp[i][j] && j-i+1 > ans.size()) 
                        ans = s.substr(i, j - i + 1);
                }
            }
            return ans;
        }
    };
    
    // 方法二，中心扩展
    // 时间复杂度 O(n2), 空间复杂度O(1)
    class Solution_2
    {
    public:
        string longestPalindrome(string s) 
        {
            int len = s.size();
            if(len == 0 || len == 1)
                return s;
    
            int start = 0;//记录回文子串起始位置
            int end = 0;//记录回文子串终止位置
            int mlen = 0;//记录最大回文子串的长度
            for(int i = 0; i < len; i++)
            {
                int len1 = expendaroundcenter(s, i, i); //一个元素为中心
                int len2 = expendaroundcenter(s, i, i + 1); //两个元素为中心
                mlen = max(max(len1, len2), mlen);
                if(mlen > end - start + 1)
                {
                    start = i - (mlen - 1) / 2;
                    end = i + mlen / 2;
                }
            }
    
            //该函数的意思是获取从start开始长度为mlen长度的字符串
            return s.substr(start, mlen);
        }
    
    private:
        int expendaroundcenter(string s,int left,int right)
        //计算以left和right为中心的回文串长度
        {
            int L = left;
            int R = right;
            while(L >= 0 && R < s.length() && s[R] == s[L])
            {
                L--; R++;
            }
    
            return R - L - 1;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, string str, string expect)
    {
        Solution_2 s;
        string result = s.longestPalindrome(str);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string str = "aa";
        string expect = "aa";
        test("Test1()", str, expect);
    }
    
    void Test2()
    {
        string str = "abcdcba";
        string expect = "abcdcba";
        test("Test2()", str, expect);
    }
    
    void Test3()
    {
        string str = "babad";
        string expect = "bab";
        test("Test3()", str, expect);
    }
    
    void Test4()
    {
        string str = "bananas";
        string expect = "anana";
        test("Test3()", str, expect);
    }
    
    void Test5()
    {
        string str = "cbbd";
        string expect = "bb";
        test("Test5()", str, expect);
    }
    
    NAMESPACE_LONGESTPALINDROMEEND
    // 测试 用例 END
    //
    void LongestPalindrome_Test()
    {
        cout << "------ start 5.最长回文子串 ------" << endl;
        NAME_LONGESTPALINDROME::Test1();
        NAME_LONGESTPALINDROME::Test2();
        NAME_LONGESTPALINDROME::Test3();
        NAME_LONGESTPALINDROME::Test4();
        NAME_LONGESTPALINDROME::Test5();
        cout << "------ end 5.最长回文子串 --------" << endl;
    }

**执行结果：**

![20200721200734621.png][]

[https_leetcode-cn.com_problems_longest-palindromic-substring]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/6acb2689bfaf47a080d27f5f904f968d.png
[20200721200734621.png]: https://img-blog.csdnimg.cn/20200721200734621.png