Lt 面试题 01.04. 回文排列

面试题 01.04. 回文排列

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。 
示例 1：

输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）

思路

排序

排序后，两两删除，判断最后剩下的数组长度是否为 1 或 0

哈希表

遍历计数后筛选出不为偶数的元素个数，出现个数至多只能 1 个

哈希表优化

实际上不需要储存个数，如果存在就删除，如果不存在就设置，最后直接统计哈希表中的元素即可。

set

同上

解答

排序

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function (s) {
  s = s.split("").sort();
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === s[i + 1]) {
      s.splice(i, 2);
      i -= 2;
    }
  }
  return s.length <= 1;
};

哈希表

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function (s) {
  const map = new Map();
  for (const arr of s) map.set(arr, map.has(arr) ? map.get(arr) + 1 : 1);
  return [...map.values()].filter((e) => e % 2 !== 0).length <= 1;
};

哈希表优化

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function (s) {
  const map = {};
  for (const arr of s) {
    if (map[arr]) delete map[arr];
    else map[arr] = true;
  }
  return Object.keys(map).length <= 1;
};

set

var canPermutePalindrome = function (s) {
  const set = new Set();
  for (const arr of s) {
    if (set.has(arr)) set.delete(arr);
    else set.add(arr);
  }
  return set.size <= 1;
};