# Leetcode 647 - Palindromic substrings

Note

• DP
• dp[i][j] means s[i - j] is a palindrome string.
• When s[i] == s[j]
• When the length of s[i, j] is 1 or 2. For example, a or aa, it must be a palindrome.
• When the length of s[i, j] is bigger than 2, it then depends on s[i+1, j-1], which is dp[i+1][j-1]. It also means that we need to iterate i from big to small.

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example

Brute Force

DP