内容简介:本题是给定一个字符串,求可以用其中字符组成的最长回文长度。Link:思路:
本题是给定一个字符串,求可以用其中字符组成的最长回文长度。
Link: https://leetcode.com/problems/longest-palindrome/
思路:
1,暴力破解,挨个枚举,时间复杂度O(n!)
2, 用hashtable记录每个字符出现的次数,成对出现(2的倍数)即视为可组成回文,最终落单的+1放中间,时间复杂度O(n)
比如:’abccccdd’
a: 1 b: 1 c: 4 d: 2
最终转换成
a: 1 b: 1 c: 0 d: 0
代码:
function getCounts(s) { const hashtable = {}; let char = null; for (let idx = 0; idx < s.length; idx++) { char = s[idx]; if (hashtable[char]) { hashtable[char]++; } else { hashtable[char] = 1; } } return hashtable; } var longestPalindrome = function(s) { const table = getCounts(s); let left = 0; let count = 0; for (const key in table) { const item = table[key]; count += Math.floor(item / 2); table[key] = item % 2; left += table[key]; } if (left > 0) { return count * 2 + 1; } else { return count * 2; } };
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
CSS3 For Web Designers
Dan Cederholm / Happy Cog / 2010-11 / $18
From advanced selectors to generated content to the triumphant return of web fonts, and from gradients, shadows, and rounded corners to full-blown animations, CSS3 is a universe of creative possibilit......一起来看看 《CSS3 For Web Designers》 这本书的介绍吧!