题目 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” 思路 题目就就做最长的回文子串，题目没有说清楚的是当一个串的最长回文子串长度为1时，输出串的第一个字符。 代码思路解析： 用start，end来标记每一次循环时一个子串的起始和终止索引，令i= start, j = end,然后逐个字符比较，符合回文条件的子串用一个字符串str保存起来并记录最长的回文串，注意当记录的最长子串大于end-start+1时，直接退出当前一层的循环(不加这个限制，程序会超时) 题目边界条件注意 : 串s长度 < 2时 直接return s; 代码
string find(string s){ if(s.size() < 2) return s; //串长度小于2，return s; int i,j,len,start,end; int maxLen = 1; len = s.size(); string str = s.substr(0,1); //若该串的最长回文串长度为1，返回第一个字符 for(start = 0; start < len - 1; start++){ //记录子串的开始位置 for(end = len-1; end > start ; end--){ //记录子串的结束位置 if(end-start+1 <= maxLen) break; //当找到的子串maxLen >= 子串的长度时，直接break; i = start; j = end; while(s[i] == s[j] && i < j){ i++; j--; } if(i >= j && maxLen < end - start + 1){ //当找到更长的子串时 maxLen = end - start + 1; //记录最长子串的长度 str = s.substr(start,end-start+1); //记录该回文子串 } } } return str;}新闻热点
疑难解答
