字符串是否有回文,有没有更好的方法呢？

Question

今天我有一个非常有趣的采访问题:

给定一个字符串,您必须确定该字符串在置换时是否具有回文结构.

以下是我提出的实现.但是有更好的解决方案吗？

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");

这不可能是重复的,因为我不是直接检查是否是回文,而是检查和检查它.

Answer 1

保留一个字符映射,计算它们,看看所有字符的计数是否均匀,如果是,则可以创建一个回文

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(''));
}

Answer 2

如果字符串中的所有字母的个数均为偶数（最多只有一个除外），则您始终可以将它们重新组织为回文。我的解决方案比其他解决方案长一点，因为我试图最大限度地减少具有函数和不必要的数组创建的循环的性能开销。

aaaabbbb => aabbbbaa
aaaabbbbc => aabbcbbaa


function isPalindromable(str) {
    var map = getCharCount(str);
    var nonPairs = 0;
    for (var char in charMap) {
        if (charMap[char] % 2 != 0)
            nonPairs++;
        if (nonPairs > 1)
            return false;
    }
    return true;
}

function getCharCount(str) {
    // Number of times each string appeared
    var map = {};
    for (var i = 0; i < str.length; i++) {
        var ch = str.charAt(i);
        map[ch] = ++map[ch] || 1;
    }
    return map;
}

如果你喜欢一个衬垫（不是那么快，但有点优雅）

function isPalindromable(str) {
    var charMap = getCharCountMap(str);
    return Object.keys(charMap).filter(char => charMap[char] %2 > 0).length <= 1;
}

function getCharCountMap(str) {
    return str.split('').reduce((prev, cur) => (prev[cur] = ++prev[cur] || 1, prev) , {})
}

演出编辑

我对这三种解决方案进行了基准测试。当琴弦较短时，我的速度最慢，而对于较长的琴弦，我的速度最快。然而，工作中的一位朋友想出了一种最终最快的解决方案，可能是因为它只有一个循环但不需要排序。http://jsperf.com/can-string-be-made-into-palindrome/2

function canBePalindromeReplace(string) {
    var oddCount = 0;

    while(string.length > 0) {
        var char = string.charAt(0);
        var stringLength = string.length;
        string = string.replace(new RegExp(char, 'g'), '');
        var diff = stringLength - string.length;
        if((diff % 2) != 0) {
            oddCount++;
            if(oddCount > 1) {
                return false;
            }
        }
    }

    return true;
}