要求输入一个长度不大于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')
