Leetcode 409 Longest Palindrome

栏目: 编程工具 · 发布时间: 6年前

内容简介:本题是给定一个字符串,求可以用其中字符组成的最长回文长度。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

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》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具