首页 > 代码库 > Leetcode: Longest Palindromic Substring
Leetcode: Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
分析：
这道题跟Longest Valid Parentheses 有类似之处，不同之处在于，valid parentheses每次扩展都是两个字符，而Palindrome可以每次扩展一个字符。在动态规划算法中，valid parentheses可以用一维数组做备忘录，而palindrome需要一个二维数组。本题有时间复杂度O(n)， 空间复杂度O(n)的算法，详见leetcode.pdf page65的Manacher‘s algorithm。此处用的动态规划方法，时间复杂度和空间复杂度均为O(n^2)，但用vector做备忘数据结构会超时。代码如下：
class Solution {public: string longestPalindrome(string s) { int n = s.length(); if(n == 0) return ""; bool f[1000][1000]; int start = 0, max_len = 0; for(int j = 0; j < n; j++) for(int i = 0; i <= j; i++){ if(i == j || j - i > 1 && f[i+1][j-1] && s[i] == s[j] || i + 1 == j && s[i] == s[j]){ f[i][j] = true; if(j - i + 1 > max_len){ max_len = j - i + 1; start = i; } }else f[i][j] = false; } return s.substr(start, max_len); }};
Leetcode: Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。