647_Palindromic Substrings
647. Palindromic Substrings
Level: medium
Tag: string, dynamic programming
Question
Note: A palindrome is a word, which reads the same backward as forward.
Example1
Example2
Idea: (expand around center, dynamic programming, similar to Longest Palindromic Substring Q5)
Loop from the beginning to the end. Take each letter be the center of the substring, and find the number of palindromic substring centered by that letter.
There are two types of center:
the letter is the center, such that the palindromic substring has odd number of letters
the space on the right of the letter is the center, such that the palindromic substring has even number of letters
Complexity
Time:
Space:
Solution
Last updated