Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer. Example:
Input: “cbbd”
Output: “bb”
C++
class Solution {public: string longestPalindrome(string s) { int start=0; int length=0; string tmp; //结果 string res; for(int i=0;i<s.size();i++) { if(s.size()-i<length) { break; } //在左边找 tmp=s.substr(0,s.size()-i); start=0; for(int j=0;j<tmp.size();j++) { if(tmp.size()-2*start<length) { break; } //两边向中间靠拢,如果出现不等,则起始位前移 if(tmp[j] !=tmp[tmp.size()-j-1]) { start=j+1; } else { //比对完毕 if(tmp.size()-2*start>length && tmp.size()-1-2*j<=1 ) { length=tmp.size()-2*start; res=tmp.substr(start,length); } } } //如果是第一次,对称轴没有偏移,所以不用分左右 if(0==i) { continue; } //在右边找 tmp=s.substr(i,s.size()-i); start=0; for(int j=0;j<tmp.size();j++) { if(tmp.size()-2*start<length) { break; } //两边向中间靠拢,如果出现不等,则起始位前移 if(tmp[j] !=tmp[tmp.size()-j-1]) { start=j+1; } else { //比对完毕 if(tmp.size()-2*start>length && tmp.size()-1-2*j<=1) { length=tmp.size()-2*start; res=tmp.substr(start,length); } } } } return res; }};GO
func longestPalindrome(s string) string { var res string var tmp string var start int var length int for i:=0;i<len(s);i++{ //在左边找 if len(s)-i <= length{ break } //截取从索引0到len(s)-1-i的子串 tmp=s[0:len(s)-i] start=0 for j:=0;j<len(tmp);j++{ if tmp[j] !=tmp[len(tmp)-1-j]{ start=j+1; if len(tmp)-2*start <=length{ break } }else{ //比对结束,更新length条件 if len(tmp)-1-2*j <=1 && length<len(tmp)-2*start{ length=len(tmp)-2*start res=tmp[start:len(tmp)-start] } } } //在右边找 tmp=s[i:len(s)]//截取从索引i到len(s)-1的子串 start=0 for j:=0;j<len(tmp);j++{ if tmp[j] !=tmp[len(tmp)-1-j]{ start=j+1; if len(tmp)-2*start <=length{ break } }else{ //比对结束,更新length条件 if len(tmp)-1-2*j <=1 && length<len(tmp)-2*start{ length=len(tmp)-2*start res=tmp[start:len(tmp)-start] } } } } return res}新闻热点
疑难解答
