# 647 - Palindromic Substrings

## 解法一 - DP

``````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.

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;
}
``````

};