关于算法:leetcode647-回文子串的数量

Example 1:

Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2:

Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Note:

1. The input string length won’t exceed 1000.

办法 1: 动静规划法
参考 leetcode5 最长回文子串的动静布局：

class Solution {public int countSubstrings(String s) {int ss = s.length();
        int result = 0;
        boolean dp[][] = new boolean[ss][ss];
        for(int i=0;i<ss;i++){for(int j=0;j<=i;j++){dp[j][i] = (s.charAt(j)==s.charAt(i))&&(i-j<2||dp[j+1][i-1]==true);
                if(dp[j][i]==true){result++;}
            }
        }
        return result;
    }
}

在这里与 leetcode5 不同的中央在于第二层循环时要写 ==，因为单个字符也是一个回文子串；leetcode5 不须要写是因为最长回文字串默认最小就是 1.

办法 2: 两头扩大法
中心点扩大法分为 1 个中心点和 2 个中心点，因为 1 个中心点对应的是奇数长度的字符串，2 个中心点对应的是偶数长度的字符串。1 个中心点共有字符串长度 len 个，2 个中心点共有字符串长度 len- 1 个，所以共有中心点 2len- 1 个。

class Solution {public int countSubstrings(String s) {int ss = s.length();
        int result = 0;
        for(int i=0;i<2*ss-1;i++){
            int left = i/2;
            int right = left+i%2;
            while(left>=0&&right<ss&&s.charAt(left)==s.charAt(right)){
                result++;
                left--;
                right++;
            }
        }
        return result;
    }
}

同理此办法也能够用于 leetcode5

class Solution {public String longestPalindrome(String s) {int ss = s.length();
        int len = 0;
        String result="";
        for(int i=0;i<2*ss-1;i++){
            int left = i/2;
            int right = left+i%2;
            while(left>=0&&right<ss&&s.charAt(left)==s.charAt(right)){if(right-left+1>len){
                    len = right-left+1;
                    result = s.substring(left,right+1);
                }
                left--;
                right++;
            }
        }
        return result;
    }
}