从末尾向前算
var naiveLCS = function(str1,str2){
var result = "";
//相等先退出
if(str1.split('').length == 0 || str2.split('').length == 0){
return false;
}
if(str1.substr(-1) == str2.substr(-1)){
result = naiveLCS(str1.slice(0,-1),str2.slice(0,-1))
if(result)
result = result + str1.slice(-1);
else
result = str1.slice(-1);
return result;
}else{
var tempR1 = naiveLCS(str1.slice(0,-1),str2);
var tempR2 = naiveLCS(str1,str2.slice(0,-1));
if(tempR1 && tempR2){
return tempR1.split('').length > tempR2.split('').length ? tempR1 : tempR2;
}else{
return tempR1 ? tempR1 : tempR2;
}
}
}
var a = "12de111q";
var b = "w12e444vq";
console.log(naiveLCS(a,b));
