[Leetcode] 647. Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/description/?envType=company&envId=facebook&favoriteSlug=facebook-six-months

sol brute force

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans=0
        length=len(s)
        for i in range(length):
            for j in range(i,length):
                if s[i:j+1]==s[i:j+1][::-1]:
                    ans+=1
        return ans

sol better n^2 way

so we have 2 kind of palindromes - even or odd lengths. If the current substring is palindrome, we can extend our left and right pointers to left and right respectively and see if that s[left]==s[right]. Notice we dont check the extended subtring cuz its ineff. we just check each charcters.

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans=0
        length=len(s)
        def extend(left,right,s):
            nonlocal ans
            while left>=0 and right <length and s[left]==s[right]:
                ans+=1
                left-=1
                right+=1
        for i in range(length):
            extend(i,i,s)
            extend(i,i+1,s)
        return ans

complexity

brute force is n^3 cuz there is n for reversing string.
optimisewd is n^2 time with 1 space