Description:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
<pre>Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.</pre>
<pre>
Input: "cbbd"
Output: "bb"
</pre>
Link:
https://leetcode.com/problems/longest-palindromic-substring/#/description
题目意思：
找出最长回文子串。
解题方法：
从头遍历一遍数组，针对每个元素找出最长回文串。
Tips:
对每个元素，要分别找奇数回文串和偶数回文串。
Time Complexity：
O(N^2)时间
完整代码：
string longestPalindrome(string s) { if(s.size() == 0) return 0; int max = 0, start; for(int i = 0; i < s.size(); i++) { //odd case int temp = -1; for(int j = 0; i - j >= 0 && i + j < s.size(); j++) { if(s[i - j] != s[i + j]) break; temp = j * 2 + 1; } if(temp > max) { start =i - (temp - 1)/2; max = temp; } //even case temp = -1; for(int j = 0; i - j >= 0 && i + j + 1 < s.size(); j++) { if(s[i - j] != s[i + j + 1]) break; temp = j * 2 + 2; } if(temp > max) { start =i - (temp - 2)/2; max = temp; } } return s.substr(start, max); }
