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"
思路：
方法一：dp
1、dp【i】【j】：定义为：字符串s的substring（i，j）是否是回文
是的话为true、不是的话为false
2、则显然有递推公式
dp【i】【j】 = dp【i+1】【j-1】 && s.charAt(i) == s.charAt(j) ， j-i >= 3
dp【i】【j】 = s.charAt(i) == s.charAt(j) ，j-i < 3
3、遍历字符串计算dp【i】【j】、找到所有dp【i】【j】为true的子字符串、然后找到其中最长的
4、两个for循环、不停扩大窗口（i，j）
// keep increasing the possible palindrome string
// find the max palindrome within this window of (i,j)
方法二：由中心点向两边扩大
1、遍历字符串每一个字符
2、选中这个字符时、有两种情况
第一：以这个字符为中心往两边expand、直到不是回文为止、返回此次substring
第二：以这个字符和其后面一个字符为中心往两边expand、直到不是回文为止、返回此次的substring
3、在这个遍历的过程中、记录下最长子字符串
