题目
647. Palindromic Substrings
解法
１、对于原先长度为N的数组ss，我们构造一个虚拟数据vss(并非真是存在，不占用存储空间)，改数据长度为2N-1，构造方法如下图所示。
２、构造数据中蓝色方框表示虚拟数，其坐标无法被２整除。而真实数的坐标都是２的整数倍。
数组重构
３、设置两个指针
st和en,分别表示回文字符串的起始和结束坐标，且始终指向真实值。指针在初始状态位置相同。４、遍历构造数据，当初始状态位于虚拟数位置时，修正
st,en的位置使其指向真实值。随后在原数组中进行滑动，更新st,en，若ss[st]==ss[en]，则表示新增回文，否则迭代结束，读取构造数据下一个数据。
def countSubstrings(self, s: str) -> int:
res = 0
for i in range(2*len(s)):
if i%2!=0:
st = int(i/2)
en = st + 1
else: st = en = int(i/2)
while st>=0 and en<len(s):
if s[st]==s[en]:
res, st, en = res+1, st-1, en+1
else: break
return res
网友评论