最长回文子串_最长回文子串——manacher 算法 - CSDN
精华内容
参与话题
  • 动态规划:最长回文子串 & 最长回文子序列

    万次阅读 多人点赞 2018-10-20 15:56:44
    一、题目 所谓回文字符串,就是一个字符串,从...最长回文子串 和 最长回文子序列(Longest Palindromic Subsequence)是指任意一个字符串,它说包含的长度最长的回文子串和回文子序列。 例如:字符串 “ABCDDCEFA...

    一、题目

    所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如 “a”、“aba”、“abba”。

    对于一个字符串,其子串是指连续的一段子字符串,而子序列是可以非连续的一段子字符串。

    最长回文子串最长回文子序列(Longest Palindromic Subsequence)是指任意一个字符串,它说包含的长度最长的回文子串和回文子序列。

    例如:字符串 “ABCDDCEFA”,它的 最长回文子串 即 “CDDC”,最长回文子序列 即 “ACDDCA”。

    二、最长回文子串

    1. 思路

    首先这类问题通过穷举的办法,判断是否是回文子串并再筛选出最长的,效率是很差的。我们使用 动态规划 的策略来求解它。首先我们从子问题入手,并将子问题的解保存起来,然后在求解后面的问题时,反复的利用子问题的解,可以极大的提示效率。

    由于最长回文子串是要求连续的,所以我们可以假设 j 为子串的起始坐标,i 为子串的终点坐标,其中 ij 都是大于等于 0 并且小于字符串长度 length 的,且 j <= i,这样子串的长度就可以使用 i - j + 1 表示了。

    我们从长度为 1 的子串依次遍历,长度为 1 的子串肯定是回文的,其长度就是 1;然后是长度为 2 的子串依次遍历,只要 str[i] 等于 str[j] ,它就是回文的,其长度为 2;接下来就好办了,长度大于 2 的子串,如果它要满足是回文子串的性质,就必须有 str[i] 等于 str[j] ,并且去掉两头的子串 str[j+1 ... i-1] 也一定是回文子串,所以我们使用一个数组来保存以 j 为子串起始坐标,i 为子串终点坐标的子串是否是回文的,由于我们是从子问题依次增大求解的,所以求解 [i ... j] 的问题时,比它规模更小的问题结果都是可以直接使用的了。

    2. 代码

    public class Main {
      
        public static void main(String[] args) {
            String s = "cabbaeeaf";
            System.out.println(getLPS(s));
        }
          
        public static String getLPS(String s) {
            char[] chars = s.toCharArray();
            int length = chars.length;
            // 第一维参数表示起始位置坐标,第二维参数表示终点坐标
            // lps[j][i] 表示以 j 为起始坐标,i 为终点坐标是否为回文子串
            boolean[][] lps = new boolean[length][length];
            int maxLen = 1; // 记录最长回文子串最长长度
            int start = 0; // 记录最长回文子串起始位置
            for (int i = 0; i < length; i++) {
                for (int j = 0; j <= i; j++) {
                    if (i - j < 2) {
                        // 子字符串长度小于 2 的时候单独处理
                        lps[j][i] = chars[i] == chars[j];
                    } else {
                        // 如果 [i, j] 是回文子串,那么一定有 [j+1, i-1] 也是回子串
                        lps[j][i] = lps[j + 1][i - 1] && (chars[i] == chars[j]);
                    }
                    if (lps[j][i] && (i - j + 1) > maxLen) {
                        // 如果 [i, j] 是回文子串,并且长度大于 max,则刷新最长回文子串
                        maxLen = i - j + 1;
                        start = j;
                    }
                }
            }
            return s.substring(start, start + maxLen);
        }
          
    }
    

    三、最长回文子序列

    1. 思路

    子序列的问题将比子串更复杂,因为它是可以不连续的,这样如果穷举的话,问题规模将会变得非常大,我们依旧是选择使用 动态规划 来解决。

    首先我们假设 str[0 ... n-1] 是给定的长度为 n 的字符串,我们使用 lps(0, n-1) 表示以 0 为起始坐标,长度为 n-1 的最长回文子序列的长度。那么我们需要从子问题开始入手,即我们一次遍历长度 1 到 n-1 的子串,并将子串包含的 最长回文子序列的长度 保存在 lps 的二维数组中。

    遍历过程中,回文子序列的长度一定有如下性质:

    • 如果子串的第一个元素 str[j] 和最后一个元素 str[i+j] 相等,那么 lps[j, i+j] = lps[j+1, i+j-1] + 2,其中 lps[j+1, i+j-1] 表示去掉两头元素的最长子序列长度。
    • 如果两端的元素不相等,那么lps[j, i+j] = max(lps[j][i+j-1], lps[j+1][i+j]),这两个表示的分别是去掉末端元素的子串和去掉起始元素的子串。

    2. 代码

    public class Main {
     
        public static void main(String[] args) {
            String s = "cabbeaf";
            System.out.println(getLPS(s));
        }
         
        public static int getLPS(String s) {
            char[] chars = s.toCharArray();
            int length = chars.length;
            // 第一维参数表示起始位置的坐标,第二维参数表示长度,使用 0 表示长度 1
            int[][] lps = new int[length][length];
            for (int i = 0; i < length; i++) {
                lps[i][i] = 1; // 单个字符的最长回文子序列长度为1,特殊对待一下
            }
            // (i + 1) 表示当前循环的子字符串长度
            for (int i = 1; i < length; i++) {
                // j 表示当前循环的字符串起始坐标
                for (int j = 0; i + j < length; j++) {
                    // 即当前循环的子字符串坐标为 [j, i + j]
                    // 所以第一个字符是 chars[j],最后一个字符就是 chars[i + j]
                    if (chars[j] == chars[i + j]) {
                        lps[j][i + j] = lps[j + 1][i + j - 1] + 2;
                    } else {
                        lps[j][i + j] = Math.max(lps[j][i + j - 1], lps[j + 1][i + j]);
                    }
                }
            }
            // 最大值一定在以0为起始点,长度为 length - 1 的位置
            return lps[0][length - 1];
        }
         
    }
    

    最后,这题只返回了最长回文子序列的长度,一般面试题中也只是要求返回长度即可。但是如果你也想知道最长回文子序列具体是啥,这可以额外添加一个变量记录最长回文子序列是哪些字符,例如维护一个键为 lps[j][i + j],值为 String 的 map。

    展开全文
  • 给定一个字符串 s,找到 s 中最长回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: &quot;babad&quot; 输出: &quot;bab&quot; 注意: &quot;aba&quot;也是一个有效答案。 ...

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

    示例 1:

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

    示例 2:

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

    解题思路

    首先最简单的做法就是暴力解法,通过二重循环确定子串的范围,然后判断子串是不是回文,最后返回最长的回文子串即可。

    class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            max_len, result = float("-inf"), ""
            for i in range(len(s)):
                for j in range(i + 1, len(s) + 1):
                    if s[i:j] == s[i:j][::-1]:
                        if j-i > max_len:
                            max_len = j-i
                            result = s[i:j]
            return result
    

    我们直接跳过它QAQ。这个问题可以通过动态规划来解,定义函数f(i,j)f(i,j)表示区间在[i,j][i,j]内的字符串是不是回文串,其中ij表示子串在s中的左右位置。

    • f(i,j)=f(i+1,j1)  si=sjf(i,j)=f(i+1,j-1)\ 当\ s_i=s_j时

    思考边界条件,当si=sjs_i=s_{j}并且j=i+1j=i+1的时候,此时字符串由两个相同字符构成;当i=ji=j的时候,此时字符串由单个字符构成。

    class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if not s:
                return ""
    
            s_len = len(s)
            mem = [[0]*s_len for _ in range(s_len)]
            left, right, result_len = 0, 0, 0
            
            for j in range(s_len):
                for i in range(j):
                    if s[i] == s[j] and (j-i < 2 or mem[i+1][j-1]):
                        mem[i][j] = 1
                    if mem[i][j] and result_len < j-i+1:
                        result_len = j - i + 1
                        left, right = i, j
                mem[j][j] = 1
            return s[left:right+1]
    

    这种算法的时间复杂度是O(n^2),空间复杂度也是O(n^2)。有没有更好的做法呢?

    我们知道回文串是中心对称的,所以只要找到回文串的中心,然后向两边扩展即可。这里的中心位置我们要奇偶分开考虑,如果字符串长度是奇数的话,中心就只有一个元素;如果字符串是偶数的话,那么中心是两个元素。

    class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if not s or len(s) < 1:
                return ""
    
            def expandAroundCenter(left, right):
                L, R = left, right
                while L >= 0 and R <len(s) and s[L] == s[R]:
                    L -= 1
                    R += 1
                return R - L - 1
    
            left, right = 0, 0
            for i in range(len(s)):
                len1 = expandAroundCenter(i, i) # 奇数
                len2 = expandAroundCenter(i, i+1) # 偶数
                max_len = max(len1, len2)
                if max_len > right - left:
                    left = i - (max_len - 1)//2
                    right = i + max_len//2
            return s[left:right+1]
    

    还有一种思路也非常不错,可以先确定回文串的右边界i,然后以右边界i向左找回文串。假设在i之前的最长回文子串长度是l,此时我们需要分别检查i+1左侧字符串长度为l+2l+1子串是不是回文串。如果l+2是回文串,那么字符串的最大长度变成l+2,对于l+1同理。

    代码如下:

    class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            if len(s) < 2 or s == s[::-1]:
                return s
            
            start, maxlength = 0, 1
            for i in range(1, len(s)):
                odd = s[i-maxlength-1:i+1] # 检查l+2
                even = s[i-maxlength:i+1]  # 检查l+1
                if i-maxlength-1 >= 0 and odd == odd[::-1]:
                    start = i-maxlength-1
                    maxlength += 2
                elif i-maxlength >= 0 and even == even[::-1]:
                    start = i-maxlength
                    maxlength += 1
            return s[start:start+maxlength]
    

    通过maxlength我们过滤了许多不必要的重复计算,所以这个代码的效率比前面一个要快许多。

    这样我们的空间复杂度就优化到了常数级别。有没有更快的算法呢?有,使用Manacher算法,类似的思想在KMP算法中也有应用。

    我将该问题的其他语言版本添加到了我的GitHub Leetcode

    如有问题,希望大家指出!!!

    展开全文
  • 四种方法求最长回文子串

    千次阅读 2019-04-10 11:53:15
    最容易想到的就是暴力破解,求出每一个子串,之后判断是不是回文,找到最长的那个。 求每一个子串时间复杂度O(N^2), 判断子串是不是回文O(N),两者是相乘关系,所以时间复杂度为O(N^3)。 string longestPali...

    所谓回文串,就是正着读和倒着读结果都一样的回文字符串。
    比如:
    a, aba, abccba都是回文串,
    ab, abb, abca都不是回文串。

    一、暴力法

    最容易想到的就是暴力破解,求出每一个子串,之后判断是不是回文,找到最长的那个。

    求每一个子串时间复杂度O(N^2), 判断子串是不是回文O(N),两者是相乘关系,所以时间复杂度为O(N^3)。

    string longestPalindrome(string &s)
    {
        int len = s.size();                  //字符串长度
        int maxlen = 1;                      //最长回文字符串长度
        int start = 0;                       //最长回文字符串起始地址
        for(int i = 0; i < len; i++)         //起始地址
        {
            for(int j = i + 1; j < len; j++) //结束地址
            {
                int tmp1 = i, tmp2 = j;
                while(tmp1 < tmp2 && s.at(tmp1) == s.at(tmp2))//判断是不是回文
                {
                    tmp1++;
                    tmp2--;
                }
    
                if(tmp1 >= tmp2 && j - i + 1 > maxlen)
                {
                    maxlen = j - i + 1;
                    start = i;
                }
            }
        }
    
        return s.substr(start, maxlen);
    }
    
    int main()
    {
        string s;
        cout << "Input source string: ";
        cin >> s;
        cout << "The longest palindrome: " << longestPalindrome(s);
        return 0;
    }
    
    运行结果:
    Input source string: abbacdeedc
    The longest palindrome: cdeedc
    

     

    二、动态规划

    设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为:

     

    则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串,且子串起点索引为j,长度为i - j + 1。
    算法时间复杂度为O(N ^ 2)。

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    string longestPalindrome(string s)
    {
        const int n = s.size();
        bool dp[n][n];
        memset(dp, 0, sizeof(dp));
    
        int maxlen = 1;     //保存最长回文子串长度
        int start = 0;      //保存最长回文子串起点
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j <= i; ++j)
            {
                if(i - j < 2)
                {
                    dp[j][i] = (s[i] == s[j]);
                }
                else
                {
                    dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]);
                }
    
                if(dp[j][i] && maxlen < i - j + 1)
                {
                    maxlen = i - j + 1;
                    start = j;
                }
            }
        }
    
        return s.substr(start, maxlen);
    }
    
    int main()
    {
        string s;
        cout << "Input source string: ";
        cin >> s;
        cout << "The longest palindrome: " << longestPalindrome(s);
        return 0;
    }

     

    三、中心扩展法

    中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法复杂度为O(N^2)。
    需要考虑两种情况:
    长度为奇数的回文串,比如a, aba, abcba
    长度为偶数的回文串,比如aa, abba

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    string longestPalindrome(string &s)
    {
        const int len = s.size();
        int maxlen = 1;
        int start = 0;
    
        for(int i = 0; i < len; i++)//求长度为奇数的回文串
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < len && s.at(j) == s.at(k))
            {
                if(k - j + 1 > maxlen)
                {
                    maxlen = k - j + 1;
                    start = j;
                }
    
                j--;
                k++;
            }
        }
    
        for(int i = 0; i < len; i++)//求长度为偶数的回文串
        {
            int j = i, k = i + 1;
            while(j >= 0 && k < len && s.at(j) == s.at(k))
            {
                if(k - j + 1 > maxlen)
                {
                    maxlen = k - j + 1;
                    start = j;
                }
    
                j--;
                k++;
            }
        }
    
        return s.substr(start, maxlen);
    }
    
    
    int main()
    {
        string s;
        cout << "Input source string: ";
        cin >> s;
        cout << "The longest palindrome: " << longestPalindrome(s);
        return 0;
    }

    三、中心扩展法

    中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法复杂度为O(N^2)。
    需要考虑两种情况:
    长度为奇数的回文串,比如a, aba, abcba
    长度为偶数的回文串,比如aa, abba

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    string longestPalindrome(string &s)
    {
        const int len = s.size();
        int maxlen = 1;
        int start = 0;
    
        for(int i = 0; i < len; i++)//求长度为奇数的回文串
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < len && s.at(j) == s.at(k))
            {
                if(k - j + 1 > maxlen)
                {
                    maxlen = k - j + 1;
                    start = j;
                }
    
                j--;
                k++;
            }
        }
    
        for(int i = 0; i < len; i++)//求长度为偶数的回文串
        {
            int j = i, k = i + 1;
            while(j >= 0 && k < len && s.at(j) == s.at(k))
            {
                if(k - j + 1 > maxlen)
                {
                    maxlen = k - j + 1;
                    start = j;
                }
    
                j--;
                k++;
            }
        }
    
        return s.substr(start, maxlen);
    }
    
    
    int main()
    {
        string s;
        cout << "Input source string: ";
        cin >> s;
        cout << "The longest palindrome: " << longestPalindrome(s);
        return 0;
    }

     

    四、Manacher算法

    Manacher算法的时间复杂度为O(N),具体可参考:

    https://blog.csdn.net/S_999999/article/details/83472651

    #include <iostream>  
    #include <cstring>
    #include <algorithm>  
     
    using namespace std;
     
    char s[1000];
    char s_new[2000];
    int p[2000];
     
    int Init()
    {
        int len = strlen(s);
        s_new[0] = '$';
        s_new[1] = '#';
        int j = 2;
     
        for (int i = 0; i < len; i++)
        {
            s_new[j++] = s[i];
            s_new[j++] = '#';
        }
     
        s_new[j] = '\0';  // 别忘了哦
        
        return j;  // 返回 s_new 的长度
    }
     
    int Manacher()
    {
        int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
        int max_len = -1;  // 最长回文长度
     
        int id;
        int mx = 0;
     
        for (int i = 1; i < len; i++)
        {
            if (i < mx)
                p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
            else
                p[i] = 1;
     
            while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断,因为左有'$',右有'\0'
                p[i]++;
     
            // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
            if (mx < i + p[i])
            {
                id = i;
                mx = i + p[i];
            }
     
            max_len = max(max_len, p[i] - 1);
        }
     
        return max_len;
    }
     
    int main()
    {
        while (printf("请输入字符串:\n"))
        {
            scanf("%s", s);
            printf("最长回文长度为 %d\n\n", Manacher());
        }
        return 0;
    }
    

     

    展开全文
  • 动态规划之最长回文子串

    千次阅读 2020-08-26 18:37:20
    给出一个字符串S,求S的最长回文子串的长度。 样例 字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。         还是先看暴力解法:枚举子串的两个端点i和j,...

    问题:

    给出一个字符串S,求S的最长回文子串的长度。
    

    样例

    字符串"PATZJUJZTACCBCC"的最长回文子串为"ATZJUJZTA",长度为9。
    

            还是先看暴力解法:枚举子串的两个端点i和j,判断在[i, j]区间内的子串是否回文。从复杂度上来看,枚举端点需要0(n2),判断回文需要0(n),因此总复杂度是O(n3)。终于碰到一个暴力复杂度不是指数级别的问题了!但是O(n)的复杂度在n很大的情况依旧不够看。
            可能会有读者想把这个问题转换为最长公共子序列(LCS) 问题来求解:把字符串S倒过来变成字符串T,然后对S和T进行LCS模型求解,得到的结果就是需要的答案。而事实上这种做法是错误的,因为一旦S中同时存在一个子串和它的倒序,那么答案就会出错。例如字符串S= “ABCDZJUDCBA”,将其倒过来之后会变成T = “ABCDUJZDCBA”,这样得到最长公共子串为"ABCD",长度为4,而事实上S的最长回文子串长度为1。因此这样的做法是不行的。
    动态规划解决
            令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串,是则为1,不是为0。这样根据S[i]是否等于S[j],可以把转移情况分为两类:
             ①若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串,S[i+1]至S[j-1]就是回文子串;如果S[i+1]至S[j-1]不是回文子串,则S[i]至S[j]一定不是回文子串。
             ②若S[i]!=S[j],那S[i]至S[j]一定不是回文子串。
    由此可以写出状态转移方程
    在这里插入图片描述

    边界dp[i][i]=1,dp[i][i+1]=(S[i]==S[i+1])?1:0 。
    

            到这里还有一个问题没有解决,那就是如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ - 1]已经被计算过,从而无法得到正确的dp[i][i]。
             如图11-4所示,先固定i=0,然后枚举j从2开始。当求解dp[0][2]时,将会转换为dp[1][],而dp[1][1]是在初始化中得到的;当求解dp[0][3]时,将会转换为dp[1][2], 而dp[1][2]也是在初始化中得到的;当求解dp[0][4]时,将会转换为dp[1][3], 但是dp[1][3]并不是已经计算过的值,因此无法状态转移。事实上,无论对ij和j的枚举顺序做何调整,都无法调和这个矛盾,因此必须想办法寻找新的枚举方式。
            根据递推写法从边界出发的原理,注意到边界表示的是长度为1和2的子串,且每次转移时都对子串的长度减了1,因此不妨考虑按子串的长度和子串的初始位置进行枚举,即第一遍将长度为3的子串的dp值全部求出,第二遍通过第一遍结果计算出长度为4的子串的dp值…这样就可以避免状态无法转移的问题。如图11-5所示,可以先枚举子串长度L (注意: L是可以取到整个字符串的长度S.len()的),再枚举左端点i,这样右端点i+ L- 1也可以直接得到。

    在这里插入图片描述
    代码:

    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1000;
    char S[maxn];//A存序列,dp[i]存以i为结尾的连续序列的最大和
    int dp[maxn][maxn];
    int main()
    {
    	gets(S);//从下标为1开始读入
    	int len=strlen(S),ans=1;
    	memset(dp,0,sizeof(dp));
    	for(int i=0;i<len;i++)
    	{
    		dp[i][i]=1;
    		if(i<len-1)
    		{
    			if(S[i]==S[i+1])
    				{
    					dp[i][i+1]=1;
    					ans=2;//初始化时注意当前最长回文子串长度;
    				}
    		}
    	}
    	//状态转移方程
    	for(int L=3;L<=len;L++)//枚举子串长度
    		for(int i=0;i+L-1<len;i++)//枚举子串起始端点 起始端点加上子串长度(子串长度包括他
    		本身,所以要-1)必须小于总长,
    			{
    				int j=i+L-1;//子串右端点
    				if(S[i]==S[j]&&dp[i+1][j-1]==1)
    				{
    					dp[i][j]=1;
    					ans=L;//更新最长回文子串长度;
    				}
    			}
    		cout<<ans<<endl;
    }
    
    展开全文
  • 子串:小于等于原字符串长度由原字符串中任意个连续字符组成的子序列 回文:关于中间字符对称的文法,即“aba”(单核)、“cabbac”(双核)等 最长回文子串:1.寻找回文子串;2.该子串是回文子串中长度最长的。一、O...
  • 最长回文子串(C/C++)

    千次阅读 2016-05-23 15:52:53
    最长回文子串(C/C++)
  • 如何找到字符串中的最长回文子串

    千次阅读 多人点赞 2018-10-02 00:39:10
    作者 |channingbreeze责编 | 胡巍巍小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。可是努...
  • 笔试面试算法经典--最长回文子串

    万次阅读 2017-04-30 10:35:40
    字符串的最长回文子串,是指一个字符串中包含的最长的回文子串。例如“1212134”的最长回文子串是“12121”。下面给出了三种求最长子串的方法。解法1(中心扩展法)时间复杂度O(n^2),空间复杂度为O(1)。中心扩展...
  • 问题描述:给你一个字符串str,若子串s是回文串,则称s为str的回文子串,求s的最大长度 解法一:暴力匹配  对每一个字符,假定位置为i,匹配判断i+1与i-1位置是否相等,相等ans长度加一,否则停止。    对奇数...
  • 动态规划算法求最长回文子串

    万次阅读 多人点赞 2016-07-31 17:21:36
    给出了动态规划方法求最长回文子串的程序及分析。
  • 【Leetcode】Python实现最长回文子串

    千次阅读 2018-05-21 18:21:53
    根据回文的特性,一个大回文按比例缩小后的字符串也必定是回文,比如ABCCBA,那BCCB肯定也是回文。所以我们可以根据动态规划的两个特点: (1)把大问题拆解为小问题 (2)重复利用之前的计算结果 这道题。如何...
  • 给定一个字符串s,找到s中最长回文子串。你可以假设s的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 分析 初始状态: dp[i...
  • 基于Python实现对求解最长回文子串的动态规划算法 1、题目    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: "babad" 输出: "bab"...
  • 什么是 回文串 和 最长回文子串

    千次阅读 2016-05-02 10:48:23
    回文串回文串就是指一串字符,无论是从前往后读或者从后往前读都是一样的比如说“wow”,“level”,不会因为读的前后顺序而不同最长回文子串指的是字符串中一个子串,它是一个回文串,而且是最长的回文串比如说,...
  • 【005-Longest Palindromic Substring(最长回文子串)】给定一个字符串S,找出它的最大的回文子串,你可以假设字符串的最大长度是1000,而且存在唯一的最长回文子串。动态规划法,  假设dp[ i ][ j ]的值为true,...
  • #include #include #include ...给定一个字符串,求它的最长回文子串的长度,并打印出最长回文子串 */ int main() { char str[99]="test"; gets(str); int strLength=strlen(str); int maxStr=0;
  • 给定一个字符串 s,找到 s 中最长回文子串。你可以假设 s 的最大长度为1000。 示例 1: 输入: “babad” 输出: “bab” 注意: &quot;aba&quot;也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” ...
  • LeetCode中有这么一道题:给定一个字符串 s,找到 s 中最长回文子串。你可以假设 s 的最大长度为1000。示例 1:输入: "babad"输出: "bab"注意: "aba"也是一个有效答案。示例 2...
  • 输出最长回文子串(找到最长回文子串,并输出最长回文子串
  • 最长回文子串——动态规划

    千次阅读 2020-01-05 10:21:59
    给定一个字符串 s,找到 s 中最长回文子串。你可以假设s 的最大长度为 1000。 示例 1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2: 输入: "cbbd" 输出: "bb" 思路:使用动态规划 设...
1 2 3 4 5 ... 20
收藏数 14,907
精华内容 5,962
关键字:

最长回文子串