# 647 - Palindromic Substrings

解法一 - DP

這題的解法基本上跟 # 5 一模一樣，只是每次把某一格設成 true 時，順便把 count++ 就可以。直接看程式碼。

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        int n = s.length();
        if(n <= 0) return 0;

        // Init
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i=0; i<n; i++) {
            dp[i][i] = true;
            count++;
        }

        // Build dp table
        for(int start=n-1; start>=0; start--) {
            for(int end=start+1; end<n; end++) {
                if(s[start] == s[end]) {
                    if(end-start==1 || dp[start+1][end-1]) {
                        dp[start][end] = true;
                        count++;
                    }
                }
            }
        }

        return count;
    }
};

這個解法的效率不怎麼樣，所以我們需要來學習一下別的解法：

Runtime: 16 ms, faster than 46.96% of C++ online submissions for Palindromic Substrings. Memory Usage: 9.9 MB, less than 48.00% of C++ online submissions for Palindromic Substrings.

解法二 - 從中間擴展

Leetcode solution 寫得還不錯，直接拿來用一下：

直接上個程式碼：

class Solution {
public:
    int countSubstrings(string s) {
        int N = s.length(), ans = 0;

        for (int center = 0; center <= 2*N-1; ++center) {
            int left = center / 2;
            int right = left + center % 2;
            while (left >= 0 && right < N && s[left] == s[right]) {
                ans++;
                left--;
                right++;
            }
        }

        return ans;
    }
};

效率有夠猛：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Palindromic Substrings. Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Palindromic Substrings.

不過上面這個寫法的 left & right 值實在很不直覺，用下面這個寫法可能比較好懂：

class Solution { public: int countSubstrings(string s) { int count = 0;

      for (int i = 0; i < s.size(); ++i) {
          // odd length palindromes 
          //since center will be one element which both left and right start at
          count += extract_palindrome(s, i, i);

          // even length palindromes 
          // because center will have two elements (which must match) since left and right differ by 1 
          count += extract_palindrome(s, i, i + 1);
    }

    return count;
}

int extract_palindrome(string s, int left, int right) {
    int count = 0;

    while (left >= 0 && right < s.size() && s[left] == s[right]) {
      --left;
      ++right;
      // add palindrome to a hash since to deduplicate (keys can be iterated over later)
      ++count;
    }

    return count;
  }

};