LeetCode5:Longest Palindromic Substring

zhihua_bupt

于 2015-10-20 00:44:24 发布

阅读量594

点赞数

分类专栏： DataStructure&Algorithms LeetCode LeetCode算法分析

本文链接：https://blog.csdn.net/geekmanong/article/details/49259157

版权

DataStructure&Algorithms 同时被 3 个专栏收录

131 篇文章

订阅专栏

LeetCode算法分析

128 篇文章

订阅专栏

LeetCode

123 篇文章

订阅专栏

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.

一、题目描述

求最长回文子字符串，意思是从给定字符串中找出最长的回文子串，例如，字符串”abcdcbef“，它的最长回文子串就是"bcdcb"

二、解题思路

动态规划的经典例子

class Solution {
public:
	string longestPalindrome(string s) {
		const int n = s.size();
		bool f[n][n];
		fill_n(&f[0][0], n*n, false);
		size_t max_len = 1, start = 0;

		for (size_t i = 0; i < s.size(); i++){
			f[i][i] = true;
			for (size_t j = 0; j < i; j++){
				f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1]));
				if (f[j][i] && max_len < (i - j + 1)){
					max_len = i - j + 1;
					start = j;
				}
			}
		}
		return s.substr(start, max_len);
	}
};