LeetCode 409——最长回文串

1. 题目

LeetCode 409——最长回文串

2. 解答

我们先来看一看回文子串的规律,如果回文子串的长度为偶数,那么其中所有的每个元素都出现了偶数次;如果回文子串的长度为奇数,那么有一个元素出现了奇数次而其余每个元素都出现了偶数次。

所以我们需要做的就是遍历一遍字符串,统计每个元素出现的次数。这里只有大写字母和小写字母,我们用一个大小为 52 的数组充当散列表即可。

最后我们就可以得出偶数的元素有多少个,再看看有没有多余的一个奇数元素就得到了能组成的最长回文序列。

int longestPalindrome(string s) {

    int n = s.size();
    if (n == 0) return 0;
    int table[52] = {0};
        
    for (int i = 0; i < n; i++)
    {
        int index = int(s[i] - 'A');
        if (s[i] >= 'a')    index -= 6;
        table[index]++;
    }

    int even = 0;
    int odd = 0;
    for (int i = 0; i < 52; i++)
    {
        even += table[i] / 2 * 2;
        odd += table[i] % 2;     
    }
    
    odd = odd > 0 ? 1: 0;
    return even + odd;
}

获取更多精彩,请关注「seniusen」!

LeetCode 409——最长回文串

上一篇:数据结构——散列


下一篇:Java之——分数累加(奇偶)