最长回文串

2022 年 10 月 04 日
广西
本文字数：787 字
阅读完需：约 3 分钟

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1 和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试顶级公司的用户准备的。来源

第 6 天

最长回文串

难度：简单

题目

给定一个包含大写字母和小写字母的字符串 s ，返回通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

示例 1:输入:s = "abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:输入:s = "a"输入:1

复制代码

题解

首先用一个 map 来统计一下各个字母出现的次数：

 let strMap = {};for(let i=0;i<s.length;i++){    if(s[i] in strMap){        strMap[s[i]] += 1;    } else {        strMap[s[i]] = 1;    }}

复制代码

如果 s 串字符都是偶数个，那么整个长度。

如果长度有奇数，则将字符出现的次数减去一，使它出现的次数为偶数次，然后加起来；

最后，如果存在奇数，则在最终结果加 1 ；

得结果即为最大的长度~

JavaScript 实现：

var longestPalindrome = function(s) {    let ans = 0;    let odd = false;    let strMap = {};    for(let i=0;i<s.length;i++){        if(s[i] in strMap){            strMap[s[i]] += 1;        } else {            strMap[s[i]] = 1;        }    }        for(let key in strMap) {        if(strMap[key] % 2 === 0) {            ans += strMap[key];        } else {            odd = true;            ans += strMap[key]-1;        }            }    if(odd) {        ans+=1;    }    return ans;};

复制代码

总结

统计字符出现次数用 map，统计最长长度是多少，而不是最长的是哪个，这个事先要明确。

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/a981ea85e68379d6fef88d4f3】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

真正的大师，永远怀着一颗学徒的心（易）

发布

暂无评论

创作场景

最长回文串

第 6 天

最长回文串

题目

题解

总结

掘金安东尼

评论