LeetCode - 409 - 最长回文串
409. 最长回文串(Longest Palindrome)
一、题目
难度:简单
语言: PHP
题目内容:
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
“abccccdd”
输出:
7
解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。二、解题
LeetCode给定函数体
class Solution { /** * @param String $s * @return Integer */ function longestPalindrome($s) { } }
- 解题
思路:计算每个字母出现次数,将奇数减一,使之变为0或偶数,再将次数相加,若回文数长度为偶数且上个循环中有减1,则可加到回文数中间。
class Solution {
/**
* @param String $s
* @return Integer
*/
function longestPalindrome($s) {
$arr = str_split($s);
$value = array_count_values($arr);
$length = 0;
$reduct = 0;
foreach ($value as $k => $item) {
if ($value[$k] % 2 !== 0) {
$value[$k] -= 1;
$reduct++;
}
$length += $value[$k];
}
if ($reduct > 0 && $length % 2 === 0) {
$length += 1;
}
return $length;
}
}
提交结果:
声明
博客文章皆为本人码字原创,在文章创作过程中借鉴了其他学者论文、专著及其他文献等,本人皆会在参考文献中注明,如若侵犯您版权,请联系本人删除。转载本内容需注明出处!
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: