问题描述
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
解决思路
中心扩散法，即从中间一个数，不断地比较左右两边是否相等，若相等，则加入回文数，不断的向左向右移动。若不等，则当前中间数组成的回文数结束，将中间数向下移动一次，重复以上。需要注意的是，组成回文数的middle charater要分单数个（ababa）和双数个（abba）
代码
class Solution {
String res = "";
public String longestPalindrome(String s) {
//corner case
if(s == null || s.length() == 0) return s;
for(int i = 0; i < s.length(); i++){
//Diffussion from the single middle
helper(s, i ,i);
//Diffussion from the double middle
helper(s, i ,i + 1);
}
return res;
}
public void helper(String s, int left, int right){
//when the left and right is a Palindromic Substring
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
//record the palidromes
String cur = s.substring(left + 1, right);
//Update the palindromes
if(cur.length() > res.length()){
res = cur;
}
}
}
效率探究
时间效率：O(n^2)
空间效率：O(n^2)
