今天我有一个非常有趣的采访问题：
Given a string,you have to determine whether that string could have a palindrome when permuted.
以下是我提出的实现.但是有更好的解决方案吗？
function canBePalindrome(someStr) {
if (typeof someStr !== "string") {
throw new Error("Expecting argument to be a string !");
}
if (someStr.length == 1) return someStr;
var canBePalin = false;
var _chunks = someStr.split("");
var _length = _chunks.length;
for (var i = 0; i < _length; i++) {
for (var j = i + 1; j < _length; j++) {
var temp_char = _chunks[i];
_chunks[i] = _chunks[j];
_chunks[j] = temp_char;
if (isPalindrome(_chunks.join(""))) return true;
}
}
return canBePalin;
} //End of canBePalindrome
function isPalindrome(someStr) {
//console.log("Checking for:"+someStr);
var original = someStr.split("");
return someStr === original.reverse().join("");
} //End of isPalindrome
canBePalindrome("mdadm");
这不可能是重复的,因为我不是直接检查是否是回文,而是检查和检查它.
解决方法
保留一个字符映射,计算它们,看看所有字符的计数是否均匀,如果是,则可以创建一个回文
function canBePalindrome(someStr) {
var map = {};
var arr = someStr.split('');
arr.forEach(function(s) {
s in map ? map[s]++ : map[s] = 1;
});
var len = Object.keys(map).filter(function(o) {
return map[o] % 2;
}).length;
return arr.length % 2 ? len === 1 : len === 0;
}
上面的“高尔夫”版本将是
function canBePalindrome(someStr) {
return (function(m,a,l) {
a.forEach(function(s) { s in m ? m[s]++ : m[s] = 1 });
l = Object.keys(m).filter(function(o) { return m[o] % 2 }).length;
return a.length % 2 ? l === 1 : l === 0;
})({},someStr.split(''));
}
