最长回文子串
一，题目
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
代码语言：javascript复制输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
代码语言：javascript复制输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
二，我的解法（暴力解法）
代码语言：javascript复制class Solution {
public String longestPalindrome(String inputStr) {
String result = inputStr.substring(0, 1);
String aimStr = "";
int tail = 0;
int head = 0;
int length = inputStr.length();
if (inputStr != null && !inputStr.isEmpty()) {
// String[] nums = buildNums(inputStr);
for (int i = 0; i < length; i ) {
tail = i 1;
head = i;
if (head > 0 && tail < length && inputStr.charAt(head - 1) == (inputStr.charAt(tail))) {
head--;
while (head >= 0 && tail < length && inputStr.charAt(head) == (inputStr.charAt(tail))) {
head--;
tail ;
}
}
System.out.println("head: " head 1);
System.out.println("tail: " tail);
aimStr = inputStr.substring(head 1, tail);
if (aimStr.length() > result.length()) {
result = aimStr;
}
tail = i 1;
head = i;
while (head >= 0 && tail < length && inputStr.charAt(head) == (inputStr.charAt(tail))) {
head--;
tail ;
}
System.out.println("head: " head 1);
System.out.println("tail: " tail);
aimStr = inputStr.substring(head 1, tail);
if (aimStr.length() > result.length()) {
result = aimStr;
}
}
}
return result;
}
}三，官方解法（动态规划）
代码语言：javascript复制public class Solution{
public String longestPalindrome(String s){
int len = s.length();
if(len < 2){
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化：所有长度为1的字串都是回文串
for(int i=0;i<len;i ){
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
//递推开始
//先枚举子串长度
for(int L = 2;L<=len;L ){
//枚举左边界，左边界的上限设置可以宽松一些
for(int i = 0 ;i<len;i ){
//由 L 和i可以确定有边界，即 j-i 1=L得
int j = L i -1;
//如果右边界越界，就可以退出当前循环
if(j >= len){
break;
}
if(charArray[i] != charArray[j]){
dp[i][j] = false;
}else{
if(j-i<3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i 1][j-1];
}
}
//只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if(dp[i][j] && j-i 1>maxLen){
maxLen = j-i 1;
begin = i;
}
}
}
return s.substring(begin,begin maxLen);
}
}
