1930. Unique Length-3 Palindromic Subsequences
1930. Unique Length-3 Palindromic Subsequences
看到回文的題目,通常都可以很直覺的想要用雙指針來做題目,可是這一個題目,我們要找的是長度為 3 的回文,我的直覺是想雙指針,可是這個方法這邊我一開始就有點卡住。不知道該怎麼做,是要靠動態規劃嗎?還是遞迴的方式去檢查?
我就先想了遞迴的方式,我先固定最左邊,去看最右邊是不是跟最左邊一樣,如果不一樣我就往內縮,那如果一樣呢?這樣看起來我不需要遞迴下去,可是在最左邊與最右邊中間可能還有很長的字串,我要怎麼處理?
在這裡我又再卡住了一次,到了這裡我才發現,不對,題目給的條件其實是在幫助我們,因為我們要找的回文長度只要 3 ,所以如果說一個字串的左邊和右邊都確定了,那我只要知道中間有幾種不同的組合。
例如下面的字串,當我們確定最左最右都是 a
的時候,中間還有四個字串,但是是其實只是 b, a, c
三個的排列組合。
abbaca
1. aba
2. aaa
3. aca
觀察到這個組合後,其實自己覺得有進了一步,但是其實不知道這個觀察是有用還是沒有用的。
在這裡我的確又再卡住了一次,我仔細想想題目的限制,我們再次觀察上面的字串的時候,其實 aba
這個字串可以出現兩次,但是我們其實只能算一次,觀察到這裡,我就觀察到了另外一個現象,那就是以這個字串為例,如果我已經觀察過了 a
,那中間如果還有左右都是 a
的回文,其實都只是已經觀察做的子集合。所以我從另外一個角度想到了,我是不是應該從 a
到 z
的去計算,先看看有沒有兩邊都是 a 的回文,有的話,我找到最左邊與最右邊的 a
,然後就可以套入上面計算有幾種排列組合的方法,如果沒有,那就代表沒有兩頭為 a
的回文,接著繼續考慮 b
依此類推,接著算到 z
。
這樣硬寫其實應該是寫得出來的,到了這部之後,我們就可以比較有效率的來解決題目了,因為上面窮舉的條件,其實還要考量兩個點,例如,我看 a
的時候,如果 a
只出現了一次,那就代表了不可能有以 a
為兩側的回文,跳過不考慮,第二點是,s
可能根本沒有包含 a
到 z
的每一個字元,如果沒有的話,那我就也可以跳過,這兩個點我就可以一起考量。
{% hint style="info" %} 如果一個字母沒有出現兩次以上的話,我們就直接跳過不考慮 {% endhint %}
到了這裡其實才是問題的核心,我們要去算字串 s
,每個字串的頻率為何,這時候這個題目的核心就會變成用 Hash Table
解題,以字母為 key
以頻率為 value
,存入 Hash Table
,接著我們就去判斷每個 c
是否有出現兩次,如果有,我們找到最左邊的 index
,最右邊的 index
,接著計算出中間到底有哪些排列組合,並加總起來,就會是題目要求的,一個字串中有哪些長度為三的回文!
class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
if len(s) < 3:
return 0
elif len(s) == 3:
return 1 if s[0] == s[2] else 0
else:
counter = Counter(s)
ans = 0
for key, val in counter.items():
if val >= 2:
leftIndex = s.index(key)
rightIndex = s.rindex(key)
ans += len(set(s[leftIndex+1:rightIndex]))
return ans