题目：
给定一个字串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了