继续打卡算法题，今天学习的是第LeetCode的第5题最长回文子串，这道题目是道中等题,第4题是困难题，默认跳过了，哈哈哈。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码能力有一些帮助。
分析一波题目
这个题目考查的回文，回文串(i,j)有一个特点，它的临近子串(i+1,j-1)也是一个回文串，比如回文串abba，那么bb也是一个回文。
这个题目如果使用暴力解法，也就是穷举，也是可以做出来的，我们应该会想到两层循环，每次计算以每个字符开始，到最后一个元素，循环出所有的子串，并记录最大的回文串。
以cbbd为例子，从前往后找子串，把每个元素开头的所有情况都穷举出来。
以c开头的字符串
c
cb
cbb
cbbd
以第一个b开头
b
bb
bbd
以第二个b开头
b
bd
以d开头
d
上面是从头往后遍历，查找回文的过程。发现有一个特点，从前往后找的字符串子串都在后面。
假如我们是从后往前找呢？ 这样前面的往前找的子字符串之前就出现了，这是个巧妙的地方。
我们试着从后往前找子串。还是上面cbbd的例子
以d开头
d
以倒数第一个b开头
b
bd
以第二个b开头
b
bb
bbd
以c开头的字符串
c
cb
cbb
cbbd
这样看就很有特点了。后面遍历的子串，前面都已经遍历过了。这样我们只要把前面遍历过的子串记录下来，这样就可以减少很多重复的判断。
这种根据子问题求解的情况，其实属于动态规划算法。
我们可以使用一个二维数组来表示字符串是否是回文串。
boolean[][] strArr = new int[length][length];
还是以cbbd为例子。
strArr[0][0] = true 代表第一个字c是回文串。
strArr[0][1] = false 代表cb不是回文。
假设我们使用i,j为下标，分别从后往前开始填这个二维数组。下面以abaab为例
编码实现
class Solution {
public String longestPalindrome(String A) {
//记录最长回文串的长度
int max = 0;
//记录最长回文串的开始位置
int start = 0;
boolean[][] arr = new boolean[A.length()][A.length()];
for(int i=A.length()-1; i>=0; i--) {
for(int j=i; j<A.length(); j++) {
//遇到了两个相同的字符，可能是回文，进一步判断
if(A.charAt(i) == A.charAt(j)) {
//遇到一个相同的或者连续的，如果是同个元素，则arr[i][j] 是回文
if(j - i <= 1) {
arr[i][j] = true;
//记录最大的回文位置
max = Math.max(max, j-i+1);
if(max == j-i+1) {
start = i;
}
} else if(arr[i+1][j-1]) {
//不是同1个元素,判断子串是不是回文，是回文则a[i][j]也是回文
arr[i][j] = true;
//记录最大的回文位置
max = Math.max(max, j-i+1);
if(max == j-i+1) {
start = i;
}
}
}
}
}
//substring(start,end) 下标从0开始，返回值不包含end位置的元素
//"hamburger".substring(4, 8) returns "urge"
//"smiles".substring(1, 5) returns "mile"
System.out.println(start+"---");
return A.substring(start,start+max);
}
}
总结
通过举例推导，找规律，这是求解很多算法问题的思路，特别是不太熟悉的题目。
