欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

#leetcode刷题之路5-最长回文子串

程序员文章站 2022-07-05 16:13:12
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。 示例 2:输入: "cbbd"输出: "bb" 思路一:暴力法,不说了 思路二:动态规划 参考官方给的思路: How c ......

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

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

示例 2:
输入: "cbbd"
输出: "bb"

思路一:暴力法,不说了

思路二:动态规划

参考官方给的思路:

how can we reuse a previously computed palindrome to compute a larger palindrome?
if “aba” is a palindrome, is “xabax” and palindrome? similarly is “xabay” a palindrome?
complexity based hint:
if we use brute-force and check whether for every start and end position a substring is a palindrome we have o(n^2) start - end pairs and o(n) palindromic checks. can we reduce the time for palindromic checks to o(1) by reusing some previous computation.

#include <iostream>
#include <vector>
using namespace std;

string longestpalindrome(string s) {
    int len=s.length();
    //std::cout << "len="<<len<< std::endl;
    int num=1;//记录长度
    int flag=0;//记录起始位置
    if(len==0) return "";
    if(len==1) return s;    //字符串只有一个的话返回那一个字符
    vector< vector<int> > palindrome(len,vector<int>(len));//用于存储回文信息,全部初始为0
    //int *palindrome=new int[len][len];
    //首先这里考虑如果整个字符串都没有回文序列,那么就返回任意一个符号,如果有两个挨着的字符相同,那么就返回其中一组
    for(int i=0;i<len;i++)
    {
        palindrome[i][i]=1;
        if((i<len-1)&&s[i]==s[i+1])
        {
            palindrome[i][i+1]=1;
            num=2;
            flag=i;
        }
    }
    for (int new_num = 3; new_num <= len; new_num++)//接着从3开始设置子串的长度
    {
        for (int j = 0; j+new_num-1 < len; j++)//枚举子串的起始点
        {
            if (s[j] == s[j+new_num-1] && palindrome[j+1][j+new_num-1-1]==1)//有点递归的感觉
            {
                palindrome[j][j+new_num-1] = 1;
                flag=j;
                num = new_num;
            }
        }
    }
    return s.substr(flag,num);

}

int main() {
    std::string s="ac";
    string ss=longestpalindrome(s);
    std::cout << ss << std::endl;
    return 0;
}

 c++二维数组动态申请内存