LeetCode - 409 - 最长回文串

409. 最长回文串(Longest Palindrome)

一、题目

  • 难度简单

  • 题目链接leetcode-cn.com/problems/longest-p...

  • 语言: PHP

  • 题目内容

    给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
    在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
    注意:
    假设字符串的长度不会超过 1010。
    示例 1
    输入:
    “abccccdd”
    输出:
    7
    解释:
    我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

    二、解题

  • LeetCode给定函数体

    class Solution {
    
      /**
       * @param String $s
       * @return Integer
       */
      function longestPalindrome($s) {
    
      }
    }
  1. 解题

    思路:计算每个字母出现次数,将奇数减一,使之变为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;
    }
}

提交结果:

PHP

声明

博客文章皆为本人码字原创,在文章创作过程中借鉴了其他学者论文、专著及其他文献等,本人皆会在参考文献中注明,如若侵犯您版权,请联系本人删除。转载本内容需注明出处!

本作品采用《CC 协议》,转载必须注明作者和本文链接
lemon_lyue
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!