JavaScript求解最长回文子串的方法分享

目录
  • 题目描述
  • 题解
  • 解决方案
    • 思路一:暴力法
    • 思路二:最长公共字串
    • 思路三:中心拓展
    • 思路四:Manacher 算法

题目描述

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

示例 1:

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

示例 2:

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

题解

回文:指一个正读和反读都相同的字符串,例如,“aba” 是回文,而 “abc” 不是。

解决方案

思路一:暴力法

即通过双重遍历来获取目标字符串所有的子串,push 到一个数组里面,然后根据字符串长度排序,从最长字串开始循环校验,第一个为回文的子串就是我们要的结果

复杂度分析

  • 时间复杂度:O(n^3)
  • 空间复杂度:O(1)
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let m = []
    let res = ''
    for(let i=0; i<s.length; i++) {
        for(let j = i; j < s.length; j++) {
            m.push(s.slice(i, j+1))
        }
    }
    m.sort(function(a,b){
        return b.length - a.length
    })
    for (let i of m) {
        if (i === i.split('').reverse().join('')) {
            res = i
            break;
        }
    }
    return res
}

上面代码在目标字符串长度过大的时候,会超出时间限制,远远超出O(n^2) 的理想时间复杂度,这是因为过多的for 循环,js 自带函数使用过多造成的,优化一下

var longestPalindrome = function(s) {
    let m = []
    let res = ''
    for(let i=0; i<s.length; i++) {
        for(let j = i; j < s.length; j++) {
            if (s[i] != s[j]) break
            let ele = s.slice(i, j+1)
            if (ele === ele.split('').reverse().join('') && ele.length > res.length) {
                res = ele
            }
        }
    }
    return res
}

看起来好多了,但是依然通不过Leecode 的测试,我觉得必须要把 slice split reverse join 这些函数都干掉才行,也可能 JS 语言效率确实慢一些

思路二:最长公共字串

反转 S,使之变成 S'。找到 S 和 S' 之间最长的公共子串,判断是否是回文

复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let rs = s.split('').reverse().join('')
    let size = s.length
    let len = 0
    let end = 0
    let a = new Array(size)
    for (let i = 0; i < size; i++) {
        a[i] = new Array()
    }
    for (let i = 0; i < size; i++) {
        for(let j = 0; j < size; j++) {
            if (s[i] === rs[j]) {
                if (i > 0 && j > 0) {
                    a[i][j] = a[i-1][j-1] + 1
                } else {
                    a[i][j] = 1
                }

                if(a[i][j] > len) {
                    let beforeIndex = size - 1 - j
                    if (beforeIndex + a[i][j] -1 == i) {
                        len = a[i][j]
                        end = i
                    }
                }
            } else {
                a[i][j] = 0
            }
        }
    }
    return s.slice(end-len+1, end+1)
}

思路三:中心拓展

遍历一遍字符串,以每个字符为中心向两边判断,是否为回文字符串

复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let size = s.length
    let start = 0
    let len = 0 //字串长度
    // 奇数长度的回文字串
    for (let i = 0; i < size; i++) {
        let left = i - 1
        let right = i + 1
        while (left >= 0 && right < size && s[left] == s[right]) {
            left --
            right ++
        }
        if (right - left - 1 > len) {
            start = left +1
            len = right -left -1
        }
    }
    // 偶数长度的回文字串
    for (let i = 0; i < size; i++) {
        let left = i
        let right = i + 1
        while (left >= 0 && right < size && s[left] == s[right]) {
            left--
            right++
        }
        if (right -left -1 > len) {
            start = left + 1
            len = right -left -1
        }
    }
    return s.slice(start, start + len)
}

思路四:Manacher 算法

manacher 算法涉及中心拓展法、动态规划,是manacher 1975年发明出来用来解决最长回文子串的线性算法

// 第一步
var longestPalindrome = function(s) {
    let size = s.length
    if (size < 2) {
        return s
    }
    let str = addBoundaries(s, '#')
    let formatSize = 2 * size +1
    let maxSize = 1

    let start = 0
    for (let i=0; i<formatSize; i++) {
        let curSize = centerSpread(str, i)
        if (curSize > maxSize) {
            maxSize = curSize
            start = (i - maxSize)/2
        }
    }
    return s.slice(start, start + maxSize)
}

// 处理原字符串
var addBoundaries = function(s, divide) {
    let size = s.length
    if (size === 0) {
        return ''
    }
    if (s.indexOf(divide) != -1) {
        throw new Error('参数错误,您传递的分割字符,在输入字符串中存在!')
    }
    return divide + s.split('').join(divide) + divide
}

// 辅助数组
var centerSpread = function(s, center) {
     // left = right 的时候,此时回文中心是一个空隙,回文串的长度是奇数
    // right = left + 1 的时候,此时回文中心是任意一个字符,回文串的长度是偶数
    let len = s.length
    let i = center - 1
    let j = center + 1
    let step = 0
    while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
        i--
        j++
        step++
    }
    return step
}
longestPalindrome('ababadfglldf;hk;lhk')

manacher 算法的工作,就是对上面代码中的辅助数组 p 进行优化,使时间复杂度的降到O(n^2)

// 完整
var longestPalindrome = function(s) {
    let size = s.length
    if (size < 2) {
        return s
    }
    let str = addBoundaries(s, '#')
    let formatSize = 2 * size +1

    let p = new Array(formatSize).fill(0)

    let maxRight = 0
    let center = 0

    let maxSize = 1

    let start = 0
    for (let i=0; i<formatSize; i++) {
        if (i < maxRight) {
            let mirror = 2 * center - i;
            // Manacher 算法的核心
            p[i] = Math.min(maxRight - i, p[mirror]);
        }
        // 下一次尝试扩散的左右起点,能扩散的步数直接加到 p[i] 中
        let left = i - (1 + p[i]);
        let right = i + (1 + p[i]);

        // left >= 0 && right < formatSize 保证不越界
        // str.charAt(left) == str.charAt(right) 表示可以扩散 1 次
        while (left >= 0 && right < formatSize && str.charAt(left) == str.charAt(right)) {
            p[i]++;
            left--;
            right++;

        }
        // 根据 maxRight 的定义,它是遍历过的 i 的 i + p[i] 的最大者
        // 如果 maxRight 的值越大,进入上面 i < maxRight 的判断的可能性就越大,这样就可以重复利用之前判断过的回文信息了
        if (i + p[i] > maxRight) {
            // maxRight 和 center 需要同时更新
            maxRight = i + p[i];
            center = i;
        }
        if (p[i] > maxSize) {
            // 记录最长回文子串的长度和相应它在原始字符串中的起点
            maxSize = p[i];
            start = (i - maxSize) / 2;
        }
    }
    return s.slice(start, start + maxSize)
}

var addBoundaries = function(s, divide) {
    let size = s.length
    if (size === 0) {
        return ''
    }
    if (s.indexOf(divide) != -1) {
        throw new Error('参数错误,您传递的分割字符,在输入字符串中存在!')
    }
    return divide + s.split('').join(divide) + divide
}
longestPalindrome('babb')

到此这篇关于JavaScript求解最长回文子串的方法分享的文章就介绍到这了,更多相关JavaScript最长回文子串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • js如何找出字符串中的最长回文串

    本文实例为大家分享了js找出字符串中的最长回文串的具体代码,供大家参考,具体内容如下 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <title>回文</title> <link rel=&q

  • JS使用栈判断给定字符串是否是回文算法示例

    本文实例讲述了JS使用栈判断给定字符串是否是回文算法.分享给大家供大家参考,具体如下: /*使用栈stack类的实现*/ function stack() { this.dataStore = [];//保存栈内元素,初始化为一个空数组 this.top = 0;//栈顶位置,初始化为0 this.push = push;//入栈 this.pop = pop;//出栈 this.peek = peek;//查看栈顶元素 this.clear = clear;//清空栈 this.length

  • js回文数的4种判断方法示例

    前言 判断一个整数是否是回文数.回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数. 例如: 121,是回文数. 1221, 是回文数. 1234,不是回文数. -121,也不是回文数. 一些特殊的情况: 0-9的数字,都可以称为回文. 不等于0,且尾数是0的数字,都不是回文. 负数都不是回文. 1. 字符串的转换 1.1 简单点,使用高阶函数来完成 思路: 先将数字转成字符串A,再经过变成数组,数组反转,数组变成字符串B三步操作之后,比较字符串A和B,得出结论. /** * @par

  • javascript基础练习之翻转字符串与回文

    翻转字符串 翻转字符串(Reverse a String),就是把字符串倒序处理的意思,比如给定一个字符串"hello",翻转后应该返回"olleh". 测试用例 reverseString("hello") 应该返回 "olleh" reverseString("Greetings from Earth") 应该返回 "htraE morf sgniteerG" 实现思路 这里说最方便

  • JS实现根据文件字节数返回文件大小的方法

    本文实例讲述了JS实现根据文件字节数返回文件大小的方法.分享给大家供大家参考,具体如下: function getFileSize(fileByte) { var fileSizeByte = fileByte; var fileSizeMsg = ""; if (fileSizeByte < 1048576) fileSizeMsg = (fileSizeByte / 1024) + "KB"; else if (fileSizeByte == 104857

  • javascript判断回文数详解及实现代码

    javascript判断回文数 概要: 回文"是指正读反读都能读通的句子,它是古今中外都有的一种修辞方式和文字游戏,如"我为人人,人人为我"等.在数学中也有这样一类数字有这样的特征,成为回文数(palindrome number). 设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 注意: 1.偶数个的数字也有回文数124421     2.小数没有回文

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

  • Python3最长回文子串算法示例

    本文实例讲述了Python3最长回文子串算法.分享给大家供大家参考,具体如下: 1. 暴力法 思路:对每一个子串判断是否回文 class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) == 1: return s re = s[0] for i in range(0,len(s)-1): for j in range(i+1

  • python实现求最长回文子串长度

    给定一个字符串,求它最长的回文子串长度,例如输入字符串'35534321',它的最长回文子串是'3553',所以返回4. 最容易想到的办法是枚举出所有的子串,然后一一判断是否为回文串,返回最长的回文子串长度.不用我说,枚举实现的耗时是我们无法忍受的.那么有没有高效查找回文子串的方法呢?答案当然是肯定的,那就是中心扩展法,选择一个元素作为中心,然后向外发散的寻找以该元素为圆心的最大回文子串.但是又出现了新的问题,回文子串的长度即可能是基数,也可能好是偶数,对于长度为偶数的回文子串来说是不存在中心元

  • python实现寻找最长回文子序列的方法

    本文实例为大家分享了python实现寻找最长回文子序列,这一类的问题可以使用动态规划的方法去做,我之前应该有几篇博文都是关于回文序列的求解的,正好有可以复用的代码就懒得再用别的方法写了,直接套用,思想还是滑窗切片,很简单就是运算会多点,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:寻找最长回文子序列 ''' def slice_window(one_str,w=1): ''''' 滑窗函数 ''' r

  • python最长回文串算法

    给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

  • Python实现针对给定字符串寻找最长非重复子串的方法

    本文实例讲述了Python实现针对给定字符串寻找最长非重复子串的方法.分享给大家供大家参考,具体如下: 问题: 给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如"aaaaaaaaaaaaa"那么满足要求的输出就是a 思路: 这里的思路有两种是我能想到的 (1)从头开始遍历字符串,设置标志位,在往后走的过程中当发现和之前标志位重合的时候就回头检查一下这个新出现的子串是否跟前面字符串或者前面字符串的子串相同,相同则记录该子串并计数加1,直至处理完毕 (2)利用滑窗切

  • Python简单实现查找一个字符串中最长不重复子串的方法

    本文实例讲述了Python简单实现查找一个字符串中最长不重复子串的方法.分享给大家供大家参考,具体如下: 刚结束的一个笔试题,很简单,不多说简单贴一下具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出来一个字符串中最长不重复子串 ''' def find_longest_no_repeat_substr(one_str): ''''' 找出来一个字符串中最长不重复子串 ''' res_list=[] le

  • php找出指定范围内回文数且平方根也是回文数的方法

    本文实例讲述了php找出指定范围内回文数且平方根也是回文数的方法.分享给大家供大家参考.具体如下: 一.要求: 给出两个数值X和Y,统计在这个区间里的回文数,并且要求它们的平方根也是回文数.其中 1<= x <= y < 10 14 二.解决方法: <?php error_reporting(E_ALL); ini_set("display_errors", 1); //避免超时 set_time_limit(0); $t1=microtime(); funct

  • PHP输出两个数字中间有多少个回文数的方法

    本文实例讲述了PHP输出两个数字中间有多少个回文数的方法.分享给大家供大家参考.具体分析如下: "回文数"是一种数字.如:98789, 这个数字正读是98789,倒读也是98789,正读倒读一样,所以这个数字就是回文数. <?php for($i=10;$i<100;$i++){ $len=strlen($i); $l=1; $k=intval($len)/2+1; for($j=0;$j<$k;$j++){ if (substr($i,$j,1)!=substr($

随机推荐

其他