題目：
給定一個字串s
要找出裡面有幾個不同的三個字回文
思路：
從左邊右邊分別找一個字元第一次跟最後一次出現的位置
分別紀錄在兩個字典裡面
再遍歷一次第一個字典
因為三個字的回文最左邊跟最右邊一定一樣
所以只要找出每個left跟right中間有幾種字的總和就是答案了
Python Code:
def countPalindromicSubsequence(self,s):
dict1,dict2={},{}
ans=0
for i,char in enumerate(s):
if char not in dict1:
dict1[char]=i
dict2[char]=i
for i in dict1:
left,right=dict1[i],dict2[i]
ans+=len(set(s[left+1:right]))
return ans
結果時間複雜度空間複雜度都一坨
查了一下字串可以直接find rfind找左右第一個出現的
所以直接把一開始的s做成set
然後對set裡面每個元素在s作find跟rfind找到left跟right
再去找left跟right中間有幾個不一樣的數就好
Python Code:
def countPalindromicSubsequence(self,s):
ans=0
for i in set(s):
left,right=s.find(i),s.rfind(i)
ans+=len(set(s[left+1:right]))
return ans
剩肥肥只會用python了