首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。