起因在于写647. Palindromic Substrings时写错了，感觉跟其他回文题搞混了。特地总结一下，尤其L家和F家的。
- Palindromic Substrings
比较好理解的dp解法，dp[i][j]代表s的第i个字符到第j个字符这一个子串是不是回文，dp[1][3] = true meaning s.substring(0,3) is a palindrome, dp多开到了n+1长度为了对齐“第几个”字符这样的称谓。
用res来统计回文数，注意到dp[n][j]只有可能出现dp[n][n]这样的情况，而且dp[i][i]就是某个单字符，肯定是回文。然后进行遍历，注意到回文我们会用到dp[i+1][j-1]来求dp[i][j], 所以要有敏感度我们应该让i递减j递增来循环。所以我们的for loop是i = n - 1 ---> 0而j = i ----> n, 而且至少要清楚j >= i, 因为表示字符串的子串时substring[i,j]肯定是j >= i的，不然是invalid. 为什么if (s.charAt(i-1) == s.charAt(j-1) && (dp[i+1][j-1] || j - i < 3)){这个判断句有j - i < 3这个条件呢，比如说"abc"这个case，n=3, 我们进入for 循环，i = 2, j = 2, 我们知道dp[2][2] = true, 但是我们如果不用j - i < 3这个条件，而是只有if (s.charAt(i-1) == s.charAt(j-1) && dp[i+1][j-1] )这个条件，我们会find out dp[i+1][j -1] = dp[3][1], which is false but actually invalid. 所以我们要考虑j - i < 3的情况。"aaa"也是，你会得到类似于dp[3][1]这种没有意义的中间变量导致结果错误。
Time:O(n2); Space:O(n2)
class Solution {
public int countSubstrings(String s) {
if (s == null || s.length() == 0){
return 0;
}
int n = s.length();
boolean[][] dp = new boolean[n+1][n+1];
int count = 0;
dp[n][n] = true;
count++;
for (int i = n - 1; i >= 1; i--){
for (int j = i; j <= n; j++){
if (s.charAt(i-1) == s.charAt(j-1) && (dp[i+1][j-1] || j - i < 3)){
dp[i][j] = true;
count++;
}
}
}
return count;
}
}
这个题还有一种用expand的方法，
我们检查从每个字符开始向外扩展所能得到的odd length palindrome和even length palindrome. left = right = i这样子向两边扩展的肯定是奇数个字符，left +1 = right这种情况肯定是偶数个。注意一下写checkPalindrome这个helper method的时候检查边界条件。比如aabaa, 我们从第一个a开始检查，奇数个字符的回文只有a本身一个，下一次left pointer就越界了； 从第一个a和第二个a向外扩散的情况也只能得到一个回文。但从b开始向外扩散的奇数字符数回文就很多了，有"b","aba","aabaa"。
Time: O(N2) Space:O(1)
Palindrome: a (Count=1)
0_1500788808121_fec1dec5-ab5f-44cf-8dbd-eb2780e8d65f-image.png
Palindrome: aa (Count=2)
Palindrome: a (Count=3)
0_1500788872920_61fc20cb-0cb2-4179-8f5a-529cbad7a2ec-image.png
Palindrome: No Palindrome
Palindrome: b,aba,aabaa (Count=6)
0_1500788934388_5cc2c31d-404c-456a-a77d-1432bb0c679b-image.png
Palindrome: No Palindrome
Palindrome: a (Count=7)
0_1500789009429_f38aa5c2-17ac-47db-8fe9-b9bb4ceb1407-image.png
Palindrome: aa (Count=8)
Count = 9 (For the last character)
Answer = 9
