647. Palindromic Substrings

Question 647

https://leetcode.com/problems/palindromic-substrings/ 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:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Solution

v1. 假設每一個字母為中央時，去確認向左向右延伸時是不是回文 - 偶數字母回文時，設定中央為右半格，例如 i = 3 時，另中央為 3 和 4 中間 - 奇數字母回文時，設定中央為自己

slower 由第一個字母開始尋找，每一個字母皆往後找到最後一個 利用 s[i:j+1][::-1] 寫法將文字倒轉

faster 已知 s 會有 2*Length + 1個檢查中心點 分別為 s[1], s[1] 和 s[2] 中間, s[2], s[2] 和 s[3] 中間, s[3], .... 依序直到最後一個字母，所以每兩次會有一次在中間 在中間時 left 和 right 會分開，其餘相等

v1

class Solution:
    def countSubstrings(self, s: str) -> int:
        Length, count = len(s), 0
        
        for i in range( Length - 1 ):
            temp = 0
            while( i - temp >= 0 and i + 1 + temp < Length and s[i - temp] == s[i + 1 + temp] ):
                count += 1
                temp += 1
            
            temp = 1
            while( i - temp >= 0 and i + temp < Length and s[i - temp] == s[i + temp] ):
                count += 1
                temp += 1
                
        return count + Length

slower

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

faster

class SolutionIII:
    def countSubstrings(self, s: str) -> int:
        count, Length = 0, len(s)
        
        # there are 2*Length - 1 centers
        # s[1], between s[1] and s[2], s[2], between s[2] and s[3] ... etc
        for center in range( 2*Length - 1 ):
            left = center // 2
            right = left + center % 2
            
            while( left >= 0 and right < Length and s[left] == s[right] ):
                count += 1
                left -= 1
                right += 1
        
        return count