647. Palindromic Substrings - Medium

前往題目

思路

有兩種解法，暴力和Manacher algorithm(馬拉車)

暴力解

1. 疊代整個string
2. 把每個char都當作是中心點，用雙指針向外擴張找尋palindrome
3. 奇數長度的palindrome找一輪，偶數長度也找一輪
4. 最終就是答案

馬拉車實在是複雜，所以就跳過了

Code

class Solution {
    public int countSubstrings(String s) {
        int res = 0;

        for (int i = 0; i < s.length(); ++i) {
            // Odd length palindrome
            //Init. pointers, take 'i' as the center
            int l = i, r = i;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                ++res;
                // Expand
                --l;
                ++r;
            }

            // Even length
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                ++res;
                // Expand
                --l;
                ++r;
            }
        }
        return res;
    }
}