LI@NG

Leetcode 409 Longest Palindrome

本题是给定一个字符串,求可以用其中字符组成的最长回文长度。

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;
	}
};