回文类题目总结

2018-01-23 本文已影响20人 greatseniorsde

起因在于写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)

First Loop: