409.最长回文串

LeetCode LeetCode 哈希表 贪心 字符串
发布时间 :
字数:2k 阅读 : 评论:
  1. 409.最长回文串
    1. 409.1 题目
    2. 409.2 题解
      1. 方法一：字典计数
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：数组计数
    3. 409.3 代码
    4. 409.4 运行结果

409.最长回文串

409.1 题目

给定一个包含大写字母和小写字母的字符串 s，返回通过这些字母构造成的最长的回文串的长度。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

示例 1:

输入：s = "abccccdd"
输出：7
解释：我们可以构造的最长的回文串是 “dccaccd”，它的长度是 7。

示例 2:

输入：s = "a"
输出：1
解释：可以构造的最长回文串是 “a”，它的长度是 1。

提示:

  • 1 <= s.length <= 2000
  • s 只由小写和/或大写英文字母组成

409.2 题解

方法一：字典计数

思路

使用字典统计每个字符的出现次数。遍历字典，将每个字符出现次数的偶数部分累加（因为回文串对称）。如果存在奇数次的字符，可以在中心位置放一个，长度加一。

核心思想：回文串对称，偶数次字符全部可用，奇数次字符取偶数部分，中心可放一个奇数字符。

具体步骤：

  1. 统计每个字符的出现次数。
  2. 遍历统计结果：
    • 累加每个字符出现次数的偶数部分 count / 2 * 2
    • 如果存在奇数次字符，标记 hasOdd = true
  3. 如果 hasOdd，长度加一（中心放一个字符）。
  4. 返回最长回文串长度。

举例：对于 s = "abccccdd"：

  • 统计：{a: 1, b: 1, c: 4, d: 2}
  • a：偶数部分 0，奇数标记
  • b：偶数部分 0，奇数标记
  • c：偶数部分 4
  • d：偶数部分 2
  • 总长度：0 + 0 + 4 + 2 = 6，存在奇数，加 1
  • 结果：7

复杂度分析

  • 时间复杂度：O(n)，遍历字符串和字典。
  • 空间复杂度：O(k)，k 为不同字符数，最多 52。

代码

// 方法一：字典计数
// 创建一个字典统计每个字符出现的次数
// 遍历字典，计算回文串的长度
// 如果发现字符出现的次数是奇数说明 最长的回文串也可以是奇数
static int LongestPalindrome1(string s)
{
    // 创建一个字典用于统计每个字符出现的次数
    Dictionary<char, int> count = new Dictionary<char, int>();

    // 遍历字符串，统计每个字符出现的次数
    foreach (char c in s)
    {
        // 如果字符已经在字典中，则将其出现次数加一；否则，将其出现次数设为1
        if (count.ContainsKey(c))
            count[c]++;
        else
            count[c] = 1;
    }

    // 初始化回文串的长度为0，判断是否有奇数次的字符
    int palindromeLength = 0;
    bool hasOdd = false;

    // 遍历字典，计算回文串的长度
    foreach (var pair in count)
    {
        // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
        palindromeLength += pair.Value / 2 * 2;
        // 如果字符出现次数为奇数，将标记置为true
        if (pair.Value % 2 != 0)
            hasOdd = true;
    }

    // 如果存在出现奇数次的字符，回文串长度加一
    if (hasOdd)
        palindromeLength++;

    // 返回最长回文串的长度
    return palindromeLength;
}

方法二：数组计数

使用长度为 128 的数组统计字符出现次数（覆盖所有 ASCII 字符）。遍历数组，累加偶数部分，如果存在奇数次的字符，长度加一。

复杂度分析：

  • 时间复杂度：O(n)，遍历字符串和数组。
  • 空间复杂度：O(1)，固定长度 128 的数组。
// 方法二：数组计数
// 和字典同理 不过用ASCII码统计
static int LongestPalindrome2(string s)
{
    // 用于存储字符出现次数的数组，ASCII码最多128个字符
    int[] count = new int[128];

    // 统计每个字符出现的次数
    foreach (char c in s)
    {
        // 字符对应的ASCII码作为数组下标，出现次数加一
        count[c]++;
    }

    // 初始化回文串的长度为0，判断是否有奇数次的字符
    int palindromeLength = 0;
    bool hasOdd = false;

    // 遍历统计数组，计算回文串的长度
    foreach (int cnt in count)
    {
        // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
        palindromeLength += cnt / 2 * 2;
        // 如果字符出现次数为奇数，将标记置为true
        if (cnt % 2 != 0)
            hasOdd = true;
    }

    // 如果存在出现奇数次的字符，回文串长度加一
    if (hasOdd)
        palindromeLength++;

    // 返回最长回文串的长度
    return palindromeLength;
}

409.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

        // 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

        // 示例 1:
        // 输入: s = "abccccdd"
        // 输出: 7
        // 解释: 我们可以构造的最长的回文串是 "dccaccd"，它的长度是 7。

        // 示例 2:
        // 输入: s = "a"
        // 输出: 1

        // 示例 3：
        // 输入: s = "aaaaaccc"
        // 输出: 7

        // 提示:
        // 1 <= s.length <= 2000
        // s 只由小写 和/或 大写英文字母组成

        #endregion

        #region 测试

        // 示例 1 方法 1
        string str1 = "abccccdd";
        int result1 = LongestPalindrome1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");

        // 示例 1 方法 2
        int result1_2 = LongestPalindrome2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2 方法 1
        string str2 = "a";
        int result2 = LongestPalindrome1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");

        // 示例 2 方法 2
        int result2_2 = LongestPalindrome2(str2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3 方法 1
        string str3 = "aaaaaccc";
        int result3 = LongestPalindrome1(str3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");

        // 示例 3 方法 2
        int result3_2 = LongestPalindrome2(str3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：字典计数
    // 创建一个字典统计每个字符出现的次数
    // 遍历字典，计算回文串的长度
    // 如果发现字符出现的次数是奇数说明 最长的回文串也可以是奇数
    static int LongestPalindrome1(string s)
    {
        // 创建一个字典用于统计每个字符出现的次数
        Dictionary<char, int> count = new Dictionary<char, int>();

        // 遍历字符串，统计每个字符出现的次数
        foreach (char c in s)
        {
            // 如果字符已经在字典中，则将其出现次数加一；否则，将其出现次数设为1
            if (count.ContainsKey(c))
                count[c]++;
            else
                count[c] = 1;
        }

        // 初始化回文串的长度为0，判断是否有奇数次的字符
        int palindromeLength = 0;
        bool hasOdd = false;

        // 遍历字典，计算回文串的长度
        foreach (var pair in count)
        {
            // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
            palindromeLength += pair.Value / 2 * 2;
            // 如果字符出现次数为奇数，将标记置为true
            if (pair.Value % 2 != 0)
                hasOdd = true;
        }

        // 如果存在出现奇数次的字符，回文串长度加一
        if (hasOdd)
            palindromeLength++;

        // 返回最长回文串的长度
        return palindromeLength;
    }

    // 方法二：数组计数
    // 和字典同理 不过用ASCII码统计
    static int LongestPalindrome2(string s)
    {
        // 用于存储字符出现次数的数组，ASCII码最多128个字符
        int[] count = new int[128];

        // 统计每个字符出现的次数
        foreach (char c in s)
        {
            // 字符对应的ASCII码作为数组下标，出现次数加一
            count[c]++;
        }

        // 初始化回文串的长度为0，判断是否有奇数次的字符
        int palindromeLength = 0;
        bool hasOdd = false;

        // 遍历统计数组，计算回文串的长度
        foreach (int cnt in count)
        {
            // 每个字符出现次数的偶数部分可以用来构成回文串，直接累加
            palindromeLength += cnt / 2 * 2;
            // 如果字符出现次数为奇数，将标记置为true
            if (cnt % 2 != 0)
                hasOdd = true;
        }

        // 如果存在出现奇数次的字符，回文串长度加一
        if (hasOdd)
            palindromeLength++;

        // 返回最长回文串的长度
        return palindromeLength;
    }

    #endregion
}

409.4 运行结果

示例1 方法1 输出：7
示例1 方法2 输出：7
示例2 方法1 输出：1
示例2 方法2 输出：1
示例3 方法1 输出：7
示例3 方法2 输出：7
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏