Leetcode 409 Longest Palindrome

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

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

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

jQuery基础教程 (第4版)

jQuery基础教程 (第4版)

[美] Jonathan Chaffer、[美] Karl Swedberg / 李松峰 / 人民邮电出版社 / 2013-10 / 59.00

本书由jQuery API网站维护者亲自撰写,第一版自2008上市以来,一版再版,累计重印14次,是国内首屈一指的jQuery经典著作! 作为最新升级版,本书涵盖jQuery 1.10.x和jQuery 2.0.x。本书前6章以通俗易懂的方式讲解了jQuery的核心组件,包括jQuery的选择符、事件、动画、DOM操作、Ajax支持等。第7章和第8章介绍了jQuery UI、jQuery M......一起来看看 《jQuery基础教程 (第4版)》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具