Max Palindrome/最大回文字符串
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
console.log("Hello World!");
/**
* 求字符串所包含的最大回文数和至少要删除的字符个数
* 字符串长度<1000
* 如:google,回文数为goog,至少要删除2个字符
*/
//求的是最长公共子串(应该求最长公共子序列)
//全遍历,时间复杂度太高
function getMaxPalindrome(str){
var strReverse = str.split("").reverse().join("");
var sLen = str.length, rLen = sLen;
var palindromes = [];
for(var i=0; i<sLen; i++){
var ic = str[i];
for(var j=0; j<rLen; j++){
var jc = strReverse[j];
if(ic == jc){
var k = 1;//palindrome len
while((i+k < sLen) && (j+k < rLen)
&&(str[i+k] == strReverse[j+k])){
k++;
}
if(k > 1){
palindromes.push(str.substr(i,k));
}
}
}
}
palindromes = palindromes.sort((a,b) => b.length-a.length);
console.log(palindromes)
let p = palindromes[0]||"";
let start = p===""? -1:str.indexOf(p);
return {
str: str,
palindrome: p,
start: start,
end: start+p.length
};
}
/**
* 文本相似度匹配
* Levenshtein distance算法
*/
function getMaxPalindrome2(src){
let des = src.split("").reverse().join();
let m = src.length;
let n = des.length;
var matrix = [];
//初始化数组
for(let i=0;i<=m;i++){
matrix[i] = [];
if(!i){
for(let j=0;j<=n;j++){
matrix[0][j] = j;
}
}else matrix[i][0] = i;
}
Array.prototype.min = function() {
return Math.min.apply({},this)
}
//计算两个字符是否一样，计算左上的值
let temp;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
temp = src[i-1]==des[j-1]?0:1;
//取三个值中最小的
matrix[i][j] = [matrix[i-1][j-1]+temp, matrix[i][j-1]+1, matrix[i-1][j]+1].min();
}
}
//console.log(matrix[m][n],Math.max(m,n),src.length,des.length)
return Math.max(m,n) - matrix[m][n];
}
// for test
console.time("自己遍历ET")
console.log(getMaxPalindrome("google"))
console.timeEnd("自己遍历ET")
console.log("-----------------------split line----------------------------------")
console.time("Levenshtein ET")
console.log("min distance: "+getMaxPalindrome2("google"));
console.timeEnd("Levenshtein ET")
console.log("-----------------------split line----------------------------------")
//文章链接：求的是最长公共子,最长公共子序列
console.log("文章链接：最长公共子串,最长公共子序列:\n https://www.jianshu.com/p/4b5d7deef7fe")
JavaScript
INFO