D116 409. Longest Palindrome

题目链接

409. Longest Palindrome

题目分析

返回通过给定的字符串能组成的最长回文字符串长度。

思路

用 array_count_values 计算字母出现次数。再区分出现次数为偶数的字母和奇数次数的字母。用 array_sum 可以直接算出现了偶数次的字母。而对于出现了奇数次的字母，只能收录一个放在回文串的最中间。即需要从总和中减去 n -1。其中 n 为出现次数为奇数的字母个数。

最终代码

<?php
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function longestPalindrome($s) {$s = str_split($s);
        $amounts = array_count_values($s);
        $total = 0;
        $maxOdd = 0;
        foreach($amounts as $v){
            $total += $v;
            if($v%2 != 0){
                $total -=1;
                if($v > $maxOdd){$maxOdd = $v;}
            }
        }
        if($maxOdd!= 0){$total+=1;}
        return $total;
    }
}

这个方案只打败了 15.8% 的代码。后来改用了以下方案：

<?php
class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function longestPalindrome($s) {$s = str_split($s);
        $amounts = array_count_values($s);
        $odd = [];
        $even = [];
        array_walk($amounts, function($v, $k) use (&$odd, &$even){if($v%2 != 0){$odd[$k] = $v;
            }
            else{$even[$k] = $v;
            }
        });
        $odds = count($odd);
        if(!empty($odds)){$odds--;}
        $total = array_sum($even) + array_sum($odd) - $odds;
        return $total;
    }
}

就打败了 100% 了。收工！

若觉得本文章对你有用，欢迎用爱发电资助。