Leetcode #647

Posted on | In
**Palindromic Substrings**
Description

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example
1
2
3
Input: "abc"  
Output: 3  
Explanation: Three palindromic strings: "a", "b", "c".
Solution

Suppose there are n elements in the input string, then there would be 2*n-1 middle positions of possible palindrome.

For each center, we can check how many palindromes using this center.

Algorithm

Python

1
2
3
4
5
6
7
8
9
10
def countPalindromes(s):   
    n, count = len(s), 0
    for i in range(2 * n - 1):	
        left = i // 2  #when i is even, the center is left, also right cause left = right 
        right = left + i % 2 #when i is odd, the center is between left and right, so right = left + 1
        while left >= 0 and right < n and s[left] == s[right]: #as long as the s[left] == s[right], we can keep expanding the left and right  
            count += 1
            left -= 1
            right += 1
    return count
Complexity
  • Time Complexity: O(N^2)
  • Space Complexity: O(1)
    Not too hard, too lazy to explain.

If there is something incorrect, please let me know. And of course if you have some other good solutions, welcome to share with me...

0%