首页 > 代码库 > LeetCode-005 Longest Palindromic Substrin
LeetCode-005 Longest Palindromic Substrin
【题目】
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.
【题意】
题意是找出字符串S中最长回文子串,S最长为1000,保证有唯一解
【思路】
原字符串用特殊字符#间隔,如下所示:#a#b#c#b#d#
从字符串的第二个字符a开始, 依次搜索以当前字符串为中心的最大回文字符串半径,直到到最后第二个字符d结束
注意此字符串中找出的回文肯定是以#作为起始和结尾的。
【代码】
class Solution { public: string longestPalindrome(string s) { string news = ""; for(int i=0; i<s.length(); i++){ news += "#"; news += s[i]; } news += "#"; int maxStart = -1; //最大回文起始位置 int maxEnd = -1; //最大回文结束位置 int maxRadius = 0; //最大回文半径 int maxCenter = 1; //最大回文中心位置 int cur = 1; // 回文中心 while(cur < news.length()-1){ int radius = 0; while(cur-radius>=0 && cur+radius<=news.length()-1 && news[cur-radius]==news[cur+radius]){ radius++; } radius--; if(radius>maxRadius){ maxCenter = cur; maxRadius = radius; maxStart = cur-radius; maxEnd = cur+radius; } cur++; } // maxStart和maxEnd肯定是指向#的,因此需要转换成原文中对应字符的位置 maxStart = maxStart/2; maxEnd = maxEnd/2-1; return s.substr(maxStart, (maxEnd-maxStart+1)); } };
【思路2】
DP构造回文判别矩阵,假设A[i][j]表示S[i~j]的子串是否为回文串
转换方程A[i][j]=A[i+1][j-1] && S[i]==S[j]
然后j-i最大的子串即为解
【代码】【TIME LIMIT EXCEEDED】
/* 题意是找出字符串S中最长回文子串,S最长为1000,保证有唯一解 思路: DP 创建回文判别矩阵使用,假设A[i][j]表示S[i~j]的子串是否为回文串 转换方程A[i][j]=A[i+1][j-1] && S[i]==S[j] */ class Solution { public: string longestPalindrome(string s) { int len = s.length(); if(len==0)return ""; vector<vector<bool> > isPal(len, vector<bool>(len, false)); int maxSubStrLen=0; int maxSubStrStart=0; //初始化斜对角线,即isPal[i][i], 单个字符肯定是回文 for(int i=0; i<len; i++){ isPal[i][i]=true; if(1>maxSubStrLen){maxSubStrLen=1; maxSubStrStart=i;} } //初始化相邻字符构成的子串是否是回文 for(int i=0; i<len-1; i++){ isPal[i][i+1]=s[i]==s[i+1]; if(isPal[i][i+1] && 2>maxSubStrLen){maxSubStrLen=2; maxSubStrStart=i;} } //初始化i<j的区域 for(int i=len-3; i>=0; i--){ for(int j=len-1; j>=i+2; j--){ isPal[i][j]=isPal[i+1][j-1]&&s[i]==s[j]; if(isPal[i][j] && j-i+1>maxSubStrLen){maxSubStrLen=j-i+1; maxSubStrStart=i; } } } return s.substr(maxSubStrStart, maxSubStrLen); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。