最长回文子串

jemygraw 发布于2019-08-23 14:44 / 3125人阅读

摘要：给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。

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

示例 1：

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

示例 2：

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

用的Manacher算法

var longestPalindrome = function(s) {
    if (s.length == 0) return ""
    var str="$"
    var j = 1,mx = 0,id = 0, len = [];
    var max=0, index;
    for(var i = 0, l = s.length; i < l; i++) {
        str += "#";
        str += s[i]
    }
    str += "#"
    for (var i = 1, l = str.length; i < l; i++) {
        if(i < mx) {
            len[i] = Math.min(len[2*id - i], mx - i)
        } else {
            len[i] = 1;
        }
        while(str[len[i] + i] == str[i - len[i]]) {
            len[i]++;
        }
        if (len[i] + i > mx) {
            id = i;
            mx = len[i] + i;
            if (len[i] > max) {
                max = len[i];
                index = i;
            }
        }
    }
    return s.substr((index - max) / 2, max - 1)
};

GPU云服务器云服务器最长公共子串 java最长相同子串最长递增短信最长

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101061.html

获取最长回文子串

摘要：以下是最长回文子串的相关代码，相关逻辑已在注释中注明我们原有的字符串可能存在两种回文子串，一种是具有基数个元素例如一种是具有偶数个元素例如这样的话分情况判断比较复杂所以我们对原字符串进行扩充在相邻元素中插入特殊值插入后的原基数回文子串变成了以下是最长回文子串的Manacher‘s Algorithm相关代码，相关逻辑已在注释中注明： public static String solu...

ymyang 2019-08-19 11:46 评论0 收藏0
最长回文子串——Manacher 算法

摘要：问题定义最长回文子串问题给定一个字符串，求它的最长回文子串长度。可以采用动态规划，列举回文串的起点或者终点来解最长回文串问题，无需讨论串长度的奇偶性。 0. 问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 评论0 收藏0
Leetcode 5 Longest Palindromic Substring 最长回文子串

摘要：难度题目是说给出一个字符串求出这个字符串的最长回文的子串回文是指前后完全对称的字符串像是之类的都算是回文奇数字母的回文和偶数字母的回文中心是不一样的奇数字母比如的中心在中间字母上偶数字母比如的回文在中间两字母的中心上由此可见回文中心点实际上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 评论0 收藏0
LeetCode.5 最长回文子串(longest-palindromic-substring)(J

摘要：一题目最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。一、题目最长回文子串：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: babad输出: bab注意: aba 也是一个有效答案。示例 2：输入: cbbd输出: bb 二、我的答案思路 1.排...

Steven 2019-08-23 16:47 评论0 收藏0
LeetCode5.最长回文子串 JavaScript

摘要：最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。 LeetCode5.最长回文子串 JavaScript 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: babad 输出: bab 注意: aba 也是一个有效答案。示例 2：输入: cbbd输出: bb /*...

philadelphia 2019-08-23 14:45 评论0 收藏0