LeetCode 409 Longest Palindrome All In One
LeetCode 409 最长回文 算法题解
Solutions
// Map
function longestPalindrome(s: string): number {
const map = new Map();
let len = 0;
for(let i = 0; i < s.length; i++) {
if(map.has(s[i])){
// 配对，消元
len += 2;
map.delete(s[i]);
} else{
map.set(s[i], 1);
}
}
// 还有剩余的字符，就选择一个放到，两两配对的回文字符串的中间，结果还是回文字符串
if(map.size) {
len += 1;
}
return len;
};
// Set
function longestPalindrome(s: string): number {
const set = new Set();
let len = 0;
for(let i = 0; i < s.length; i++) {
if(set.has(s[i])){
// 配对，消元
len += 2;
set.delete(s[i]);
} else{
set.add(s[i]);
}
}
// 还有剩余的字符，就选择一个放到，两两配对的回文字符串的中间，结果还是回文字符串
if(set.size) {
len += 1;
}
return len;
};
demos
// Set / Map
function longestPalindrome(s: string): number {
const map = new Map();
let len = 0;
for(let i = 0; i < s.length; i++) {
if(map.has(s[i])){
// 配对，消元
len += 2;
map.delete(s[i]);
} else{
map.set(s[i], 1);
}
}
// 还有剩余的字符，就选择一个放到，两两配对的回文字符串的中间，结果还是回文字符串
if(map.size) {
len += 1;
}
return len;
};
// function longestPalindrome(s: string): number {
// const set = new Set();
// let len = 0;
// for(let i = 0; i < s.length; i++) {
// if(set.has(s[i])){
// // 配对，消元
// len += 2;
// set.delete(s[i]);
// } else{
// set.add(s[i]);
// }
// }
// // 还有剩余的字符，就选择一个放到，两两配对的回文字符串的中间，结果还是回文字符串
// if(set.size) {
// len += 1;
// }
// return len;
// };
// function longestPalindrome(s: string): number {
// let target = s[0];
// for(let i = 0; i < s.length; i++) {
// let char = s[i];
// let others = s.slice(0, i) + s.slice(i + 1);
// let strs = getFullPermutation(others);
// for(let str of strs) {
// if(isPalindrome(str) && str.length > target.length) {
// // console.log(`✅ str =`, str)
// target = str;
// }
// // console.log(`isPalindrome(char + str) =`, isPalindrome(char + str), char + str)
// if(isPalindrome(char + str) && (char + str).length > target.length) {
// // console.log(`✅ char + str =`, char + str)
// target = (char + str);
// }
// }
// }
// return target.length;
// };
// // 排列组合 ???
// function getFullPermutation(str: string): string[] {
// if (str.length === 1) {
// return [str];
// } else {
// const result: string[] = [];
// //遍历每一项
// for (let i = 0; i < str.length; i++) {
// // 当前的元素
// let current = str[i];
// // 其他元素 (拼接)
// let others = str.slice(0, i) + str.slice(i + 1);
// // 其他元素的全排列 （递归）
// let temp = getFullPermutation(others);
// for (let j = 0; j < temp.length; j++) {
// // 组合
// const item = current + temp[j];
// result.push(item);
// }
// }
// return result;
// }
// }
/*
https://www.cnblogs.com/xgqfrms/p/16389706.html
*/
/*
Wrong Answer
21 / 95 testcases passed
Input
s =
"abcbe"
Output
1
Expected
3
*/
const isPalindrome = (str) => {
let rs = ``;
let len = str.length;
// 逆序字符串
while(len--){
rs += str[len];
}
return str === rs;
}
// ❌
// const isPalindrome = (str = ``) => {
// const len = Math.floor(str.length / 2);
// str = str.toLocaleLowerCase();
// for (let i = 0; i < len; i++) {
// if (str[i] !== str[len - i - 1]) {
// // 提前结束
// return false;
// }
// }
// return true;
// }
// ❌
// isPalindrome(`aaaa`)
// false
// function isPalindrome(str: string): boolean {
// let l = 0;
// let r = str.length - 1;
// if(str.length <= 2) {
// return str[l] === str[r];
// }
// while(l < r) {
// if(str[l] !== str[r]) {
// break;
// }
// l++;
// r--;
// }
// return l === r;
// };
/*
回文
A palindrome is a string that reads the same forward and backward.
*/
https://leetcode.com/problems/longest-palindrome/description/