leetcode

Palindromic Substrings

Palindromic Substrings

One line Version - 924ms

1
2
3
4
5
6
7
class Solution:
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        return sum(s[i:j] == s[i:j][::-1] for j in range(len(s) + 1) for i in range(j))

O(n) Version - 128ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countSubstrings(self, S):
        """
        :type s: str
        :rtype: int
        """
        N = len(S)
        ans = 0
        for center in range(2*N - 1):
            left = center // 2
            right = left + center % 2
            while left >= 0 and right < N and S[left] == S[right]:
                ans += 1
                left -= 1
                right += 1
        return ans

test code

1
2
In [25]: s = Solution(); t = s.countSubstrings('abc'); print(t)
3

leet code