【中等】5-最长回文子串 Longest Palindromic Substring

题目

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

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

Example1

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

Example2

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

来源:力扣(LeetCode)

链接:https://leetcode.com/problems/longest-palindromic-substring

解法

方法一:中心

解题思路

对于回文字符串查找,暴力破解的方法是把所有子串找出来再排除其中不是回文子串的内容,这个方法明显是很冗余的。这道题的问题在于,一个长字符串中可以有很多回文子串,

我们并不知道最终的目标子串在哪个位置,所以找到了一条局部最长子串之后一定要继续查找确保不会出现更长的子串。如果我们从第一个字符开始逐个向后查找以该字符为起点的最长回文子串,那与暴力破解其实没有什么差别了,因为不做完全的查询和检验是没有办法说明问题的。

但是由于回文字符串具有对称的性质,如果我们从字符串的对称轴也就是最中间的元素作为查询顺序,向其两边排查是否都对称,只要有不对称的元素,我们就可以判定以该字符为中心的局部最长回文字符串是什么,进而找到最终的最长子串了。

需要注意的是,回文字符串的长度可能是奇数也可能是偶数,如果是奇数,就以一个字符为中心,如果是偶数,就以两个相同字符为中心即可。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        string substring = "";
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); ++i){
            for(int j = 1; j <= i; ++j){ // 以字符i为中心
                if(j+i<s.length() && i-j>=0){
                    if(s[j+i] == s[i-j]){
                        start = i-j;
                        end = j+i;
                    }
                    else{
                        break; // 局部最长已经找到
                    }
                }
            }
            if(end-start+1 > substring.length()) substring = s.substr(start, end-start+1);
            if(i+1<s.length() && s[i] == s[i+1]){ // 以字符i和i+1为中心(两字符相同)
                start = i;
                end = i+1;
                for(int j = 1; j <= i; ++j){
                    if(j+i+1<s.length() && i-j>=0){
                        if(s[j+i+1] == s[i-j]){
                            start = i-j;
                            end = j+i+1;
                        }
                        else{
                            break;
                        }
                    }
                }
                if(end-start+1 > substring.length()) substring = s.substr(start, end-start+1);
            }
        }
        return substring;
    }
};

方法二:动态规划

求解思路

首先分析回文子串的性质可以发现:

  1. 长度为1的子串一定是回文子串
  2. 对于一个回文子串,去掉其开头和结尾的一个字符,剩下的子串仍旧是回文子串

也就是说,如果一个字符串是回文子串,那么在这个子串两端加上相同的字符,构造出的新的字符串也是回文的,也就是说回文字符串具有可归纳的性质,由此,我们联想到使用动态规划方法,初始状态即为每一个单独的字符都是回文字符串,状态转移方程就是

f[i][j] = f[i+1][j-1] && s[i]==s[j], i<j-1
        = s[i]==s[j], i=j-1

代码

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length() < 2) return s;
        string substring = s.substr(0, 1);
        bool dp[s.length()][s.length()];
        for(int i = 0; i < s.length(); ++i){
            dp[i][i] = true;
        }
        for(int i = 1; i < s.length(); ++i){
            for(int j = 0; j < i; ++j){
                if(i-j == 1){
                    if(s[i] == s[j]){
                        dp[j][i] = true;
                        if(substring.length() < 2) substring=s.substr(j,2);
                    }
                    else{
                        dp[j][i] = false;
                    }
                }
                else{
                    if(dp[j+1][i-1] && s[i] == s[j]) {
                        dp[j][i] = true;
                        if(substring.length() < i-j+1) substring=s.substr(j, i-j+1);
                    }
                    else dp[j][i] = false;
                }

            }
        }
        return substring;
    }
};

总结

  1. 在中心扩展方法中,需要处理字符串奇偶的情况,但是如果在字符中间隔插入一个新符号如#,可以将偶数转化为奇数情况

原文地址:https://www.cnblogs.com/suata/p/12706092.html

时间: 04-15

【中等】5-最长回文子串 Longest Palindromic Substring的相关文章

[译]最长回文子串(Longest Palindromic Substring) Part II

[译+改]最长回文子串(Longest Palindromic Substring) Part II 问题:给定字符串S,求S中的最长回文子串. 在上一篇,我们给出了4种算法,其中包括一个O(N2)时间O(1)空间的算法(中心检测法),已经很不错了.本篇将讨论一个O(N)时间O(N)空间的算法,即著名的Manacher算法,并详细说明其时间复杂度为何是O(N). 提示 +BIT祝威+悄悄在此留下版了个权的信息说: 先想想有什么办法能改进中心检测法. 考虑一下最坏的情况.★ 最坏的情况就是各个回文

最长回文子串(Longest Palindromic Substring)-DP问题

问题描述: 给定一个字符串S,找出它的最大的回文子串,你可以假设字符串的最大长度是1000,而且存在唯一的最长回文子串 . 思路分析: 动态规划的思路:dp[i][j] 表示的是 从i 到 j 的字串,是否是回文串. 则根据回文的规则我们可以知道: 如果s[i] == s[j] 那么是否是回文决定于 dp[i+1][ j - 1] 当 s[i] != s[j] 的时候, dp[i][j] 直接就是 false. 动态规划的进行是按照字符串的长度从1 到 n推进的. DP算法实现: 1 packa

LeetCode 5. 最长回文子串 Longest Palindromic Substring

题目: 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb"  解法一 遍历字符串,以每个字母为中心,向两边扩散查找,记录当前最长的回文子串的长度和起始位置.结尾位置.时间复杂度O(n^2) 注意: ①当剩下的字符串长度小于当前m

【算法】最长回文子串 longest palindrome substring

对于字符串S, 要找到它最长的回文子串,能想到的最暴力方法,应该是对于每个元素i-th都向左向右对称搜索,最后用一个数组span 记录下相对应元素i-th为中心的回文子串长度. 那么问题来了: 1. 这样的方法,对于奇回文子串和偶回文子串的处理不一样,比如所"acbca" 和"acbbca" 2. 计算冗余,e.g. "sscssabcccchccccba"中, 自左向右遍历计算的话,会发现, "abcccchccccba"是

[LeetCode] 5. Longest Palindromic Substring 最长回文子串

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 最长回文子串Longest palindromic substring, 最长回文子串或最长对称因子问题是在一个字符串中查找一个最长连续子串,这个子串

转载:LeetCode:5Longest Palindromic Substring 最长回文子串

本文转自:http://www.cnblogs.com/TenosDoIt/p/3675788.html 题目链接 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 求字符串的最长回文子串 算法1:暴

[C++]LeetCode: 99 Longest Palindromic Substring (最长回文子串)

题目:Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 思路:题目要求的s的一个最长回文子串.暴力解决办法就是枚举所有的子串,再对每个子串进行回文判断.进行剪枝,我们考虑可以使用动态规划来避免重复的判

leetcode 5 :Longest Palindromic Substring 找出最长回文子串

题目: Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 翻译: 找出字符串s中最长的回文子串,字符串s的最长是1000,假设存在唯一的最长回文子串 法一:直接暴力破解 O(N3)的时间复杂度,运行超

[LeetCode]33. Longest Palindromic Substring最长回文子串

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 解法一:考虑回文字符串paliStr的特征,分为字符串长度为奇偶两种情况:(1)paliStr.size()为奇数时,则从最中间的一个字符往两边扩展是

Leetcode 5. Longest Palindromic Substring(最长回文子串, Manacher算法)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: Input: "cbbd"