【程序员面试金典】【字符串】面试题 01.04 - 回文排列
一 目录
不折腾的前端，和咸鱼有什么区别
| 目录 |
|---|
| 一 目录 |
| 二 题目 |
| 三 解题思路 |
| 四 统计分析 |
| 五 解题套路 |
二 题目
给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1：
输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-permutation-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* @param {string} s
* @return {boolean}
*/
var canPermutePalindrome = function(s) {
};
根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。
三 解题思路
两种解法：
-
Map -
Array
07:07 解法 1：Map 记忆
const canPermutePalindrome = (s) => {
const map = new Map();
for (let i = 0; i < s.length; i++) {
if (map.get(s[i])) {
map.set(s[i], map.get(s[i]) + 1);
} else {
map.set(s[i], 1);
}
}
let flag = false;
for (let i of map) {
if (i[1] % 2 !== 0 && flag) {
return false;
} else if (i[1] % 2 !== 0 && !flag) {
flag = true;
}
}
return true;
};
10:14 解法 2：数组
/**
* @param {string} s
* @return {boolean}
*/
const canPermutePalindrome = (s) => {
const newS = s.split('').sort();
const result = [];
for (let i = 0; i < newS.length; i++) {
if (result[result.length - 1] === newS[i]) {
result.pop();
} else {
result.push(newS[i]);
}
}
return result.length < 2;
};
回顾了下，好像 Map 操作可以优化一下：
const canPermutePalindrome = (s) => {
const map = new Map();
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
map.delete(s[i]);
} else {
map.set(s[i], 1);
}
}
return map.size < 2;
};
那么就到这里吧~
四 统计分析
本题不需要统计分析
五 套路分析
本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。
如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~
不折腾的前端，和咸鱼有什么区别！
jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。
浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。