首页 > 代码库 > 【LeetCode】Longest Palindromic Substring
【LeetCode】Longest Palindromic Substring
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.
同Palindrome Partitioning II 几乎一致，二维数组动态规划问题。
需要注意两点：
1、使用数组比使用vector of vector节省时间；
2、每次发现当前最优回文串就使用substr取出会耗时间，改成记录起始位置。
class Solution {public: string longestPalindrome(string s) { int n = s.size(); int longest = INT_MIN; int begin = 0; int end = 0; string ret = ""; //n*n的二维数组，isPar[i][j]代表s[i,...,j]是否为回文字符串 //初始化方式为，isPar由n个vector<bool>元素构成，每个vector<bool>由n个false构成 bool isPar[1000][1000] = {false}; for(int i = 0; i < n; i ++) isPar[i][i] = true; for(int i = n-1; i >= 0; i --) { for(int j = i+1; j < n; j ++) { if(s[i] == s[j]) { //更新isPar[i][j] if(j == i+1 || isPar[i+1][j-1] == true) { isPar[i][j] = true; if(j-i+1 > longest) { longest = j-i+1; begin = i; end = j; } } } } } return s.substr(begin, end-begin+1); }};
【LeetCode】Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。