最长回文问题

前端之家收集整理的这篇文章主要介绍了最长回文问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

要求输入一个长度不大于1000的字符串,返回字符串中的最长回文:

O(n2)解法

function logestPalindrome(str){
if(!str){
    throw new error('no string')
}
if(str.length === 1){
    return 1
}
function helper(string,begin,end){
    while(begin >= 0 && end <= string.length-1 && string[begin] === string[end]){
        begin--
        end++
    }
    return string.substring(begin+1,end)
}
var longest = str.substring(0,1)
for(var i = 0; i  longest.length){
        longest = tmp
        //console(tmp)
    }
    //console.log(i)
    tmp = helper(str,i+1)
    //console.log(tmp)
    if(tmp.length >longest.length){
        longest = tmp
    }
}
return longest.length

}
//console.log(logestPalindrome('abbacshgdisggdisgdgsyfssssddsdfhfgdgdgydgydgfydgfyfdfdfdggabbbbbbbbbba'))

O(n!)暴力枚举

function findPalindrome(str){
// extend String method to reverse the character like Array
String.prototype.reverse = function(){
    return this.split('').reverse().join('')
}
// extend String method to splice(delete) the character like Array
String.prototype.splice = function(index,num,insert){
    var that = this.split('')
    that.splice(index,insert)
    return that.join('')
}

//if a string is a palindrome
function judge(str){
if(str === str.reverse()){
return true
}
else{
return false
}
}
// wether to continue the function
var stop = false

// the function to enumerate the charater to be deleted
// c is the number of characters to be deleted
function del(str,c){
if(c ===0 && !stop){
if(judge(str)){
stop = true
console.log('Got it:'+str.length +' '+str)
return str.length
}
}
else if(c === 1 && !stop){
var string = str
var strlen = str.length
for(var i =0;i < strlen;i++){
var after = string.splice(i,1)
// console.log(after+' '+ i) //ex
if(judge(after)){
stop = true
console.log('Got it:'+after.length +' '+after)
return after.length
}
}
}
else if(c > 1 && !stop){
var str = str
var len = str.length
for(var j = 0;j<len&&!stop;j++){
// console.log(j)
var count = c
mystr = str.splice(j,1)
// console.log('Count: '+count+'str: '+mystr+' J: '+j)
del(mystr,--count)

    }
}
else{
    throw new error('error argument')
}

}

//enumerate the number of characters to be deleted

var i = 0
while (i < str.length && !stop ){
del(str,i)
i++
}
}

findPalindrome('abbaccsf')

最长回文问题还可参考:


猜你在找的程序笔记相关文章