LeetCode Longest Palindromic Substring
发布时间：2020-12-13 20:11:24 所属栏目：PHP教程 来源：网络整理
导读：Longest Palindromic Substring Question Solution 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 题意：
Longest Palindromic SubstringGiven 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.
题意：求原串中最长的回文子串 思路：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,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⑴]))
f[j][i] = 1;
if (f[j][i] && i - j + 1 > ans){
ans = i - j + 1;
start = j;
}
}
}
return s.substr(start,ans);
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |