【Leetcode 5】最长回文字串 —— 动态规划

2024-01-09 15:31:44

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);
	}
}

文章来源:https://blog.csdn.net/why_still_confused/article/details/135468531
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。