5.最长回文子串

LeetCode LeetCode 双指针 动态规划 字符串
发布时间 :
字数:2.2k 阅读 : 评论:
  1. 5.最长回文子串
    1. 5.1 题目
    2. 5.2 题解
      1. 中心扩展法
      2. 动态规划法
    3. 5.3 代码
    4. 5.4 运行结果

5.最长回文子串

5.1 题目

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

5.2 题解

中心扩展法

// 方法一：中心扩展法
// 遍历每个字符，分别以每个字符和每两个相邻字符为中心，找到最长的回文子串
// 在找到更长的回文子串时更新起始和结束索引
// 最后根据起始和结束索引，返回最长回文子串的部分。
static string LongestPalindrome1(string s)
{
    // 如果输入字符串为空，则直接返回空字符串
    if (string.IsNullOrEmpty(s)) return "";

    // 初始化起始和结束索引，用于存储最长回文子串的起始和结束位置
    int start = 0, end = 0;

    // 遍历每个字符作为中心点（奇数长度的回文串和偶数长度的回文串）
    for (int i = 0; i < s.Length; i++)
    {
        // 找到以 s[i] 为中心的最长回文子串的长度
        int len1 = ExpandAroundCenter(s, i, i);

        // 找到以 s[i] 和 s[i+1] 为中心的最长回文子串的长度
        int len2 = ExpandAroundCenter(s, i, i + 1);

        // 取两种情况中的最大长度
        int maxLength = Math.Max(len1, len2);

        // 如果找到的最大长度大于当前记录的最长回文子串长度，则更新起始和结束索引
        if (maxLength > end - start)
        {
            start = i - (maxLength - 1) / 2; // 计算起始索引
            end = i + maxLength / 2; // 计算结束索引
        }
    }

    // 返回最长回文子串
    return s.Substring(start, end - start + 1);
}

// 中心扩展函数，返回以 left 和 right 为中心的回文串长度
static int ExpandAroundCenter(string s, int left, int right)
{
    // 向两边扩展，直到不再满足回文串的条件
    while (left >= 0 && right < s.Length && s[left] == s[right])
    {
        left--; // 向左移动左边界
        right++; // 向右移动右边界
    }

    // 返回以 left 和 right 为中心的回文串的长度
    return right - left - 1;
}

动态规划法

// 方法二：动态规划法
// 创建一个二维数组 dp，其中 dp[i, j] 表示从索引 i 到 j 的子串是否为回文串。
// 首先，单个字符都是回文串，因此初始化长度为 1 的回文串。
// 然后，检查长度为 2 的子串是否为回文串。
// 最后，对长度大于 2 的子串应用动态规划递推关系：如果 s[i] 等于 s[j] 并且 s[i+1...j-1] 也是回文串，则 dp[i, j] 是回文串。
static string LongestPalindrome2(string s)
{
    // 如果输入字符串为空，则直接返回空字符串
    if (string.IsNullOrEmpty(s)) return "";

    int strLength = s.Length;
    // 创建一个二维数组 dp，dp[i, j] 表示从索引 i 到 j 的子串是否为回文串
    bool[,] dp = new bool[strLength, strLength];

    int start = 0; // 记录最长回文子串的起始位置
    int maxLength = 1; // 记录最长回文子串的长度，默认为 1

    // 单个字符都是回文串，初始化长度为 1 的回文串
    for (int i = 0; i < strLength; i++)
    {
        dp[i, i] = true;
    }

    // 检查长度为 2 的子串是否为回文串
    for (int i = 0; i < strLength - 1; i++)
    {
        if (s[i] == s[i + 1])
        {
            dp[i, i + 1] = true;
            start = i; // 更新最长回文子串的起始位置
            maxLength = 2; // 更新最长回文子串的长度
        }
    }

    // 检查长度大于 2 的子串是否为回文串
    for (int nowCheckLength = 3; nowCheckLength <= strLength; nowCheckLength++)
    {
        for (int i = 0; i <= strLength - nowCheckLength; i++)
        {
            int j = i + nowCheckLength - 1;
            // 如果 s[i] 等于 s[j] 并且 s[i+1...j-1] 也是回文串，则 dp[i, j] 是回文串
            if (s[i] == s[j] && dp[i + 1, j - 1])
            {
                dp[i, j] = true;
                start = i; // 更新最长回文子串的起始位置
                maxLength = nowCheckLength; // 更新最长回文子串的长度
            }
        }
    }

    // 返回最长回文子串
    return s.Substring(start, maxLength);
}

5.3 代码

using System;

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

        // 给你一个字符串 s，找到 s 中最长的回文子串。

        // 示例 1：
        // 输入：s = "babad"
        // 输出："bab"
        // 解释："aba" 同样是符合题意的答案。

        // 示例 2：
        // 输入：s = "cbbd"
        // 输出："bb"

        // 提示：
        // 1 <= s.length <= 1000
        // s 仅由数字和英文字母（大写和/或小写）组成

        #endregion

        #region 测试

        // 示例 1
        string s1 = "babad";
        string result1_1 = LongestPalindrome1(s1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        string result1_2 = LongestPalindrome2(s1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string s2 = "cbbd";
        string result2_1 = LongestPalindrome1(s2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        string result2_2 = LongestPalindrome2(s2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：中心扩展法
    // 遍历每个字符，分别以每个字符和每两个相邻字符为中心，找到最长的回文子串
    // 在找到更长的回文子串时更新起始和结束索引
    // 最后根据起始和结束索引，返回最长回文子串的部分。
    static string LongestPalindrome1(string s)
    {
        // 如果输入字符串为空，则直接返回空字符串
        if (string.IsNullOrEmpty(s)) return "";

        // 初始化起始和结束索引，用于存储最长回文子串的起始和结束位置
        int start = 0, end = 0;

        // 遍历每个字符作为中心点（奇数长度的回文串和偶数长度的回文串）
        for (int i = 0; i < s.Length; i++)
        {
            // 找到以 s[i] 为中心的最长回文子串的长度
            int len1 = ExpandAroundCenter(s, i, i);

            // 找到以 s[i] 和 s[i+1] 为中心的最长回文子串的长度
            int len2 = ExpandAroundCenter(s, i, i + 1);

            // 取两种情况中的最大长度
            int maxLength = Math.Max(len1, len2);

            // 如果找到的最大长度大于当前记录的最长回文子串长度，则更新起始和结束索引
            if (maxLength > end - start)
            {
                start = i - (maxLength - 1) / 2; // 计算起始索引
                end = i + maxLength / 2; // 计算结束索引
            }
        }

        // 返回最长回文子串
        return s.Substring(start, end - start + 1);
    }

    // 中心扩展函数，返回以 left 和 right 为中心的回文串长度
    static int ExpandAroundCenter(string s, int left, int right)
    {
        // 向两边扩展，直到不再满足回文串的条件
        while (left >= 0 && right < s.Length && s[left] == s[right])
        {
            left--; // 向左移动左边界
            right++; // 向右移动右边界
        }

        // 返回以 left 和 right 为中心的回文串的长度
        return right - left - 1;
    }


    // 方法二：动态规划法
    // 创建一个二维数组 dp，其中 dp[i, j] 表示从索引 i 到 j 的子串是否为回文串。
    // 首先，单个字符都是回文串，因此初始化长度为 1 的回文串。
    // 然后，检查长度为 2 的子串是否为回文串。
    // 最后，对长度大于 2 的子串应用动态规划递推关系：如果 s[i] 等于 s[j] 并且 s[i+1...j-1] 也是回文串，则 dp[i, j] 是回文串。
    static string LongestPalindrome2(string s)
    {
        // 如果输入字符串为空，则直接返回空字符串
        if (string.IsNullOrEmpty(s)) return "";

        int strLength = s.Length;
        // 创建一个二维数组 dp，dp[i, j] 表示从索引 i 到 j 的子串是否为回文串
        bool[,] dp = new bool[strLength, strLength];

        int start = 0; // 记录最长回文子串的起始位置
        int maxLength = 1; // 记录最长回文子串的长度，默认为 1

        // 单个字符都是回文串，初始化长度为 1 的回文串
        for (int i = 0; i < strLength; i++)
        {
            dp[i, i] = true;
        }

        // 检查长度为 2 的子串是否为回文串
        for (int i = 0; i < strLength - 1; i++)
        {
            if (s[i] == s[i + 1])
            {
                dp[i, i + 1] = true;
                start = i; // 更新最长回文子串的起始位置
                maxLength = 2; // 更新最长回文子串的长度
            }
        }

        // 检查长度大于 2 的子串是否为回文串
        for (int nowCheckLength = 3; nowCheckLength <= strLength; nowCheckLength++)
        {
            for (int i = 0; i <= strLength - nowCheckLength; i++)
            {
                int j = i + nowCheckLength - 1;
                // 如果 s[i] 等于 s[j] 并且 s[i+1...j-1] 也是回文串，则 dp[i, j] 是回文串
                if (s[i] == s[j] && dp[i + 1, j - 1])
                {
                    dp[i, j] = true;
                    start = i; // 更新最长回文子串的起始位置
                    maxLength = nowCheckLength; // 更新最长回文子串的长度
                }
            }
        }

        // 返回最长回文子串
        return s.Substring(start, maxLength);
    }

    #endregion
}

5.4 运行结果

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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏