首页 > 代码库 > 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.

Show Tags







题意:求原串中最长的回文子串

思路:DP做法就是:还是判断两边,往中间缩,O(n^2)的做法

class Solution {
public:
		string longestPalindrome(string s) {
            if (s.length() == 0) return "";
            
            int len = s.length();
            int f[len][len];
            memset(f, 0, sizeof(f));
            int ans = 1;
            int start = 0;

            for (int i = 0; i < len; i++) {
                f[i][i] = 1;
                for (int j = 0; j < i; j++) {
                	if (s[j] == s[i] && (i - j < 2 || f[j+1][i-1]))
                		f[j][i] = 1;
                    if (f[j][i] && i - j + 1 > ans){
                        ans = i - j + 1;
                        start = j;
                    }
                }
            }
            
            return s.substr(start, ans);
    	}
};

LeetCode Longest Palindromic Substring