魔法师 (@Constanline) 在 Leetcode每日一题 —— 2472. 不重叠回文子字符串的最大数目 中发帖
思路
模拟即可。设len为需要比较的长度,分两种情况讨论:
回文长度偶数
\text{chars}[i+x] = \text{chars}[i-x-1], \quad x \in \{0,1,\dots,\text{len}-1\}
k为奇数时,需比较长度len=k+1/2;k为偶数时,需比较长度len=k/2。
回文长度奇数
\text{chars}[i+x] = \text{chars}[i-x], \quad x \in \{1,2,\dots,\text{len}\}
无论k是奇数还是偶数,需比较长度len=k/2
如果是回文,累计结果并更新起始位置。
PS
看到困难题,以为如果没有合适算法就无法通过,结果想了半天也没想出来。那就先试试模拟,然后看看能否优化,结果水灵灵的过了,还是100%???无法理解为什么标困难!
代码
class Solution {
...