欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

[Leetcode 5] 最长回声字符串 -- 动态编程

最编程 2024-06-01 10:07:06
...

5. 最长回文字串

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

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

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

示例 2:

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

题目分析

经典动态规划问题,更多案例可见 Leetcode 动态规划详解

我们可以使用动态规划解决本题,解题思路:

  1. 状态定义:dp[l][r]表示起点为i,终点为j的字串是否回文串
  2. 状态转移方程:dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r],即dp[l + 1][r - 1]为回文串且i和j的字符相同

动态规划一般用于求解具有重叠子问题和最优子结构的问题,例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中,多次用到相同的子问题,最优子结构指的是问题的最优解可以通过子问题的最优解来构造

class Solution {
   
   
    /**
     * 状态转移方程:dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r]
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
   
   
        if (s == null || s.length() < 2) {
   
   
            return s;
        }
        int n = s.length();
        //最长回文串的起点、终点和长度
        int maxStart = 0, maxEnd = 0, maxLen = 1;
        boolean[][] dp = new boolean[n][n];
        for (int r = 1; r < n; r++) {
   
   
            for (int l = 0; l < r; l++) {
   
   
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
   
   
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
   
   
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }
}

推荐阅读