【LeetCode】5. 最长回文子串

佚名 6年前 (2019-10-24) 算法 1942人围观抢沙发百度已收录

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例

示例一

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案示例二输入: "cbbd"
输出: "bb"

解题

回文：字符串正向读和反向读是一样就叫回文

一个字符: 肯定是回文
两个字符：相等
三个字符: 首尾字符相等
四个字符: 若首尾相等 && 中间是回文
.......
Str[i,j] = str[i] == str[j] && str[i+1,j-1] == 回文

根据上面规律，想到用动态规划解决这个问题

public string LongestPalindrome(string s)
{
    if (string.IsNullOrEmpty(s) || s.Length <= 1) return s;

    var result = string.Empty;

    var dp = new bool[s.Length, s.Length];

    for (int i = s.Length - 1; i >= 0; i--)
    {
        for (int k = i; k < s.Length; k++)
        {
            dp[i, k] = s[i] == s[k] && (k - i < 2 || dp[i + 1, k - 1]);

            if (dp[i, k] && (k - i + 1) > result.Length)
            {
                result = s.Substring(i, k - i + 1);
            }
        }
    }
    return result;
}