本文主要是介绍leetcode No5. Longest Palindromic Substring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question：
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.
题目大意是找出字符串中最长的回文字符串
Algorithm：（最笨的方法）
遍历字符串，从当前字符往两边走，如果一样就继续，不一样停止并返回这个字符串的起始下标、终止下标，长度
Submitted Code：
class Solution {
public:
string longestPalindrome(string s) {
int N = s.size();
if(N<2)return s;
<span style="white-space:pre"> </span> string t;
<span style="white-space:pre"> </span> string res;
<span style="white-space:pre"> </span> int max = 0; //max length of palindromic substring
<span style="white-space:pre"> </span>int begin = 0; //begin position of max palindromic substring length
<span style="white-space:pre"> </span> int end = 0; //end position of max palindromic substring length
<span style="white-space:pre"> </span>for (int i = 0; i<(N-1); i++)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>t.push_back(s[i]);
<span style="white-space:pre"> </span>t.push_back('#'); //插入'#'的目的是为了区分奇偶
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>t.push_back(s[N - 1]);
<span style="white-space:pre"> </span>for (int j = 0; j<(2 * N - 1); j++)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>int m = j;
<span style="white-space:pre"> </span>int n = 0; //j往两边走的步数
<span style="white-space:pre"> </span>int count = 0;
<span style="white-space:pre"> </span>while ((m - n) >= 0 && (m + n)<(2 * N - 1))
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if (t[m - n] == t[m + n])
<span style="white-space:pre"> </span>count++;
<span style="white-space:pre"> </span>else
<span style="white-space:pre"> </span> break;
<span style="white-space:pre"> </span>n++;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>if (t[m-n+1] == '#')count--; //例如"#b#"多算了一次
<span style="white-space:pre"> </span>if (count>max)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>begin = m - n + 1;
<span style="white-space:pre"> </span>end = m + n - 1;
<span style="white-space:pre"> </span>max = count;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>for (int i = begin, j = 0; i <= end; i++)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if (t[i] != '#')
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>res.push_back(t[i]);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
return res;
}
};
这篇关于leetcode No5. Longest Palindromic Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
