今天 (2/10) 的 Daily 是 Medium 題： Leetcode 647. Palindromic Substrings

這題和Leetcode 5. Longest Palindromic Substring基本相同，只是從求最長變成的回文子字串變成求所有回文子字串的數量。

目錄

題目分析

題目

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

給你一個字串s，請你統計並回傳這個字串中回文子字串的數目。 回文字串是正著讀和倒過來讀一樣的字串。 子字串是字串中的由連續字元組成的一個序列。 具有不同起始位置或結束位置的子字串，即使是由相同的字元組成，也會被視為不同的子字串。

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

分析

題目相當單純，主要的思考在於如何縮減時間複雜度上。

解題思路

方案一、暴力解(brute force)

首先，遍歷所有的i,j以求得``s所有的子字串s[j:i]，並且逐一判斷子字串s[j:i]是不是回文子字串。

判斷回文最簡單的方法，可以從字串的兩端(頭尾)開始，將每個字元配對檢查。

範例程式碼

# Brute Force
class Solution:
    def countSubstrings(self, s: str) -> int:
        def isPalindrome(s):
            return all(s[i]==s[len(s)-i-1] for i in range((len(s)+1)//2))
        cnt = 0
        return [isPalindrome(s[j:i]) for i in range(1, len(s)+1) for j in range(i)].count(True)

複雜度分析

遍歷出所有的子字串需要O(n^2)，並且每次判斷是否為回文字，需要O(n)

因此，整個暴力解的時間複雜度為O(n^3)

仔細觀察暴力解的過程，會發現，在判斷是否為回文字串時產生了效能上的浪費。

舉例來說，對於s = 'abbac'，我們需要檢查'abba'，但也檢查'bb'

當檢查'abba'是個回文字時，我們先檢查兩端的'a'一致，再檢查中間的'b'。換言之，只要改變取出子字串的順序，我們是不需要再度檢查'bb'的。

方案二、對取出子字串順序的優化

在暴力解中，我們是透過遍歷子字串的開頭(j)與結尾(i-1)來取出s[j:i]。

如果改成：依序指定一個字串的中間位置，並且由此位置向兩端延展，來依序取出子字串，便可以避免前述的重複檢查。

以s = 'abcba'舉例：(Python index)

指定中間位置為0
    取出s[0:1]   =  'a'

指定中間位置為1
    取出s[1:2]   =   'b'
    取出s[0:3]   =  'abc'

指定中間位置為2
    取出s[2:3]   =    'c'
    取出s[1:4]   =   'bcb'
    取出s[0:5]   =  'abcba'

透過這種取法，因為每次都只需要比對頭、尾的一個字元，而不需要重新比對整個字串，

每次判定是否為回文字，就從暴力解的O(n)縮減成O(1)的時間。

範例程式碼： (Python 3)

# spread from mid
class Solution:
    def countSubstrings(self, s: str) -> int:
        cnt = 0
        # odd length
        for i in range(len(s)):
            j = 0
            while i-j>=0 and i+j<len(s) and s[i-j]==s[i+j]:
                cnt +=1
                j += 1
        # even length
        for i in range(len(s)):
            j = 0
            while i-j>=0 and i+j+1<len(s) and s[i-j]==s[i+j+1]:
                cnt += 1
                j += 1
        return cnt

複雜度分析

遍歷出所有的子字串需要O(n^2)，並且每次判斷是否為回文字，需要O(1)

整個策略時間複雜度為O(n^2)

方案三、動態規劃法(Manacher’s Algorithm)

利用回文字的特性，其實我們甚至並不需要遍歷所有子字串。

觀察這個字串：s = 'abacaba'

如果已知s[0:3] = 'aba'是回文字，且s[0:7] = 'abacaba'也是回文字，那麼不須任何判斷，s[4:7] = 'aba'必定是回文字。

為什麼呢？因為回文字有對稱的性質：

s = abacaba 是一個回文字，因此對其中心點i=4對稱
    aba|aba

利用這種特性，誕生出一個動態規劃法，又稱為Manacher’s Algorithm

Manacher’s Algorithm 介紹

首先我們先對s字串做一點處理：

  1. 頭尾接上一個「不同」的符號

    這是為了後續的程式碼設計方便，避免index out of range。

    根據前述spread from mid的做法，我們一旦比對到「相同」的字元就會繼續往外比對，因此故意在頭尾加上不同的(且s中沒有出現的)字元，便可以確保比對到頭、尾時停止比對。

    比起時時刻刻對index加上上下界，這種作法更簡潔。

  2. 將每個字元中間插入一個「相同」的符號

    在spread from mid時我們發現，對於奇數長度的回文字和偶數長度的回文字，處理index時的做法稍微有所不同。

    把每個字元中間加上一個符號，讓原本長度為偶數的回文字串，長度也變成奇數。

    例如abba，插入'#'後就變成#a#b#b#a#。

  3. 經過處理之後，s字串被改寫為t。此時我們定義z value：

    以某字元為中心，往外延伸可以得到最長的回文字時，所延展的長度稱為z。即對於該字元為中心來說，最長的回文字串長度為2z+1。

    我們以一個listp來記錄，其中p[i]表示以t[i]為回文字中心時的z value

    Manacher’s Algorithm 0

  4. 觀察可知，對於每個回文中心t[i]，p[i](其z value)和回文字總數的關係如下：

    1. 若t[i]為原本的字元：共有(p[i]//2 +1)個回文字
    2. 若t[i]為添加的字元：共有(p[i])//2個回文字
    1. t[i]為原本的字元
#b#a#b#
↑
z=3       (3+1)//2 = 2
以其為中心的回文字數 = 2 (bab、a)

2. t[i]為我們添加的字元
#a#b#b#a#
    ↑
    z=4           4//2 = 2
    以其為中心的回文字數 = 2(abba、bb)

  5. 那如何利用回文字對稱的特性，在O(n)時間內計算出所有位置的z值呢？

    我們由左至右逐一計算p[i]，並且追蹤兩個數值：

    1. 目前為止「抵達最右邊」的回文字，記錄其字尾的位置 r

    2. 目前為止 「抵達最右邊」的回文字的中心位置c

    以上圖的字串為例，假設我們目前計算到 i=5，準備計算i=6。

    此時，抵達最右邊的回文字串為#b#a#b#，r=7，c=4

    Manacher’s Algorithm 1

  6. 如果照著spread from mid的思維，此時我們應該比較：是否t[5]==t[7]。

    Manacher’s Algorithm 2

    但其實不需要比較！

  7. 因為t[7]包含在「抵達最右邊的回文字串」中，換言之：t[5~7]和t[3~1]是互相對稱的。

    所以，我們檢查與i=6對稱的位置i=2，並且查看已經計算過的z index：p[2]=1，這個1代表：：

    以i=2為中心，最長有一個向外延展1的回文字

    因為對稱，所以：

    以i=6為中心，最長「至少」有一個向外延展1的回文字

    注意這裡不是「最長延展1」，而是「最長至少延展1」，原因是：

    i=6延展1之後已經到7，而這個7是「目前為止抵達最右邊的回文字其字尾的位置」(r)，換言之，i=8目前還從未被考慮過。

    透過以上討論，對於p[6](i=6 的 z index)，不須比較是否t[5]==t[7]，直接從是否t[4]==t[8]開始比較。

    Manacher’s Algorithm 3

這個策略，可以整理為 Manacher’s Algorithm：

Manacher’s Algorithm

  1. 對字串s做處理，轉化為字串t

  2. p[i]紀錄以位置i為中心的 z index

  3. 對於i=0，p[i]=0

  4. 從i=1開始逐次往右計算，並且記錄抵達最右的回文字串的中心c與最右位置r

    1. 若i>=r，因為i的右邊已經超過目前所探索的範圍，直接以i為中心，從i+1開始進行spread from mid策略 alt text
    2. 若i<r：
      1. 尋找以c為軸，i的對稱點j
      2. p[j]即為p[i]的最小值
        1. 若i+p[j]<r：代表整個以j為中心的最長回文字都已探索過，因此以i為中心的最長回文字也在r的範圍內，因此p[i]=p[j] alt text
        2. 若i+p[j]>=r，從r+1開始以i為中心進行spread from mid策略 alt text
    3. 更新c與r

  5. 對於每個回文中心t[i]，p[i](其z value)和回文字總數的關係如下：

    1. 若t[i]為原本的字元：共有(p[i]//2 +1)個回文字
    2. 若t[i]為添加的字元：共有(p[i])//2個回文字

範例程式碼： (Python 3)

# spread from mid
class Solution:
    def countSubstrings(self, s: str) -> int:
        t = '#'.join(list(f'${s}^'))
        p = [0]*len(t)
        c, r = 0, 0
        for i in range(1, len(t)-1):
            z = r>i and min(r-i, p[2*c-i])
            while t[i+(z+1)] == t[i-(z+1)]:
                z+=1
            p[i] = z
            if i+z>r:
                c,r = i, i+z
        return sum(r//2 +1 if i%2==0 else (r+1)//2 for i,r in enumerate(p[2:len(p)-2]))

複雜度分析

雖然看似有兩層迴圈，實際上只對每一個r進行一次字元比對，時間複雜度為 T = O(n)

需要一個list p 來記錄所有的z value，空間複雜度亦為 S = O(n)

alt text

結語

字串相關的動態規劃每一個都很複雜，雖然幾個月前寫過Leetcode 5. 最長回文子字串，這次還是花了一點時間拿紙筆畫過一遍推演z-value的過程，才回想起Manacher’s Algorithm正確的順序。

希望透過費曼學習法，自己寫一篇blog來記錄可以加深自己的記憶。

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！