Longest Palindromic Substring（动态规划求解）

柔光的暖阳◎ 2022-06-05 06:46 178阅读 0赞

# 题目 #

Given a string **s**, find the longest palindromic substring in **s**. You may assume that the maximum length of **s** is 1000.

**Example:**

Input: "babad"
    
    Output: "bab"
    
    Note: "aba" is also a valid answer.

**Example:**

Input: "cbbd"
    
    Output: "bb"

# 分析 #

## 1. 题目要求 ##

给出一个字符串，求解出该字符串的最长回文子串。

## 2. 求解方法 ##

可以用暴力求解的方法，遍历出该字符串的所有子串，然后判断各个子串是否为回文子串，输出最大的回文子串，该方法的时间复杂度为O(n^3)。

也可以用动态规划的方法来求解其最长回文子串。其时间复杂度为O(n^2)。

使用一个 bool 类型的二维数组p，p\[i\]\[j\] 表示从 i 到 j 的子串是否为回文子串。

p\[i\]\[j\] = \{s\[i\] == s\[j\] , i - j <= 1; s\[i\] == s\[j\] && p\[i + 1\]\[j - 1\];\}

## 3. 代码如下 ##

class Solution { public: string longestPalindrome(string s) { int len = s.length(); int max_len = 0; int start = 0; bool **arr = new bool*[len]; for (int i = 0; i < len; i++) { arr[i] = new bool[len]; for (int j = 0; j < len; j++) { arr[i][j] = false; } } // 以 j 为起点， i 为结点的子串 for (int i = 0; i < len; i++) { for (int j = 0; j <= i; j++) { if (i - j < 2) { arr[j][i] = (s[i] == s[j]); } else { arr[j][i] = (s[i] == s[j] && arr[j + 1][i - 1]); } if (arr[j][i] == true && max_len < i-j+1) { max_len = i - j + 1; start = j; } } } return s.substr(start, max_len); } };

还有一种时间复杂度更低的 Manacher法，以后再说。

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode Longest Palindromic Substring

题目 Given a string S, find the longest palindromic substring in S. You may assume that

本是古典何须时尚/ 2022年08月05日 00:51/ 0 赞/ 148 阅读

相关 5 Longest Palindromic Substring

Given a string S, find the longest palindromic(adj. 回文的；复发的) substring in S. You may ass

向右看齐/ 2022年08月01日 00:11/ 0 赞/ 28 阅读

相关 LeetCode：Longest Palindromic Substring

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等

青旅半醒/ 2022年07月12日 07:43/ 0 赞/ 127 阅读

相关 LeetCode：Longest Palindromic Substring

第五题是求字符串里的最大回文子串，回文串（Palindromic Substring）就是例如”aba”，“abba”这种，网上有很多使用解决方法，比如使用动归，kmp的变种等

谁践踏了优雅/ 2022年07月12日 07:43/ 0 赞/ 110 阅读

相关 Leetcode——5. Longest Palindromic Substring

1. 概述 Given a string s, find the longest palindromic substring in s. You may assume t

柔情只为你懂/ 2022年06月15日 07:21/ 0 赞/ 188 阅读

相关 Longest Palindromic Substring（动态规划求解）

题目 Given a string s, find the longest palindromic substring in s. You may assume that

柔光的暖阳◎/ 2022年06月05日 06:46/ 0 赞/ 179 阅读

相关 LeetCode-Longest Palindromic Substring

文章目录 LeetCode-Longest Palindromic Substring 题目描述思路分析 C++实现

- 日理万妓/ 2022年03月20日 03:31/ 0 赞/ 140 阅读

相关 leetcode Longest Palindromic Substring(动态规划求解最长回文子串)

[https://leetcode.com/problems/longest-palindromic-substring/][https_leetcode.com_proble

深碍√TFBOYSˉ_/ 2022年03月17日 09:27/ 0 赞/ 236 阅读

相关 5. Longest Palindromic Substring

description: Given a string s, find the longest palindromic substring in s. You may a

旧城等待，/ 2021年12月24日 19:04/ 0 赞/ 225 阅读

相关 Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the m

青旅半醒/ 2021年12月17日 10:33/ 0 赞/ 197 阅读