这道题是LeetCode 2484. 统计回文子序列数目要求统计数字字符串中所有长度为5的回文子序列个数结果对 10^9 7 取模。思路分析长度为5的回文子序列形如 x y z y x其中 x, y, z 都是数字0-9。核心思路是枚举回文中心位置对于每个位置作为中心 z统计它左边能形成的 x y 子序列数量和右边能形成的 y x 子序列数量两者相乘再累加。具体做法1. 预处理右侧从右往左遍历维护- suf[d]当前右侧数字 d 出现的次数- suf2[d][j]当前右侧能形成的以 d 开头、j 结尾的两位数子序列数量2. 从左往右遍历每个字符作为中心时- 先撤销当前字符在右侧的贡献因为它现在变成中心了- 枚举所有可能的 x y 组合0-9累加 pre2[x][y] * suf2[x][y] 到答案- 再将当前字符加入左侧的统计中3. 维护左侧- pre[d]当前左侧数字 d 出现的次数- pre2[d][j]当前左侧能形成的以 d 开头、j 结尾的两位数子序列数量JavaScript 代码/*** param {string} s* return {number}*/var countPalindromes function(s) {const MOD 1e9 7;const n s.length;// 右侧统计const suf new Array(10).fill(0);const suf2 Array.from({ length: 10 }, () new Array(10).fill(0));// 先预处理右侧for (let i n - 1; i 0; i--) {const d parseInt(s[i]);for (let j 0; j 10; j) {suf2[d][j] suf[j];}suf[d];}// 左侧统计const pre new Array(10).fill(0);const pre2 Array.from({ length: 10 }, () new Array(10).fill(0));let ans 0;for (let i 0; i n; i) {const d parseInt(s[i]);// 当前字符作为中心从右侧移除suf[d]--;for (let j 0; j 10; j) {suf2[d][j] - suf[j];}// 枚举所有可能的 xy 组合for (let x 0; x 10; x) {for (let y 0; y 10; y) {ans (ans pre2[x][y] * suf2[x][y]) % MOD;}}// 当前字符加入左侧for (let j 0; j 10; j) {pre2[d][j] pre[j];}pre[d];}return ans;};复杂度分析- 时间复杂度O(n × 10²) O(100n)其中 n 是字符串长度。因为每次枚举所有两位组合100种但实际可以通过维护 cur 变量优化到 O(10n)- 空间复杂度O(10²) O(100)常数空间优化版本O(10n)如果追求更优的性能可以维护一个 cur 变量来避免每次枚举100种组合var countPalindromes function(s) {const MOD 1e9 7;const n s.length;const suf new Array(10).fill(0);const suf2 Array.from({ length: 10 }, () new Array(10).fill(0));for (let i n - 1; i 0; i--) {const d parseInt(s[i]);for (let j 0; j 10; j) {suf2[d][j] suf[j];}suf[d];}const pre new Array(10).fill(0);const pre2 Array.from({ length: 10 }, () new Array(10).fill(0));let ans 0;let cur 0; // 当前中心位置能贡献的回文数for (let i 0; i n; i) {const d parseInt(s[i]);// 从右侧移除当前字符suf[d]--;for (let j 0; j 10; j) {cur - pre2[d][j] * suf[j]; // 减去受影响的组合suf2[d][j] - suf[j];}ans (ans cur) % MOD;// 加入左侧for (let j 0; j 10; j) {cur pre[j] * suf2[d][j]; // 加上新增的组合pre2[d][j] pre[j];}pre[d];}return ans;};这样每次只更新与当前数字 d 相关的10种组合而不是全部100种效率更高。
千问 LeetCode 2484.统计回文子序列数目 JavaScript实现
这道题是LeetCode 2484. 统计回文子序列数目要求统计数字字符串中所有长度为5的回文子序列个数结果对 10^9 7 取模。思路分析长度为5的回文子序列形如 x y z y x其中 x, y, z 都是数字0-9。核心思路是枚举回文中心位置对于每个位置作为中心 z统计它左边能形成的 x y 子序列数量和右边能形成的 y x 子序列数量两者相乘再累加。具体做法1. 预处理右侧从右往左遍历维护- suf[d]当前右侧数字 d 出现的次数- suf2[d][j]当前右侧能形成的以 d 开头、j 结尾的两位数子序列数量2. 从左往右遍历每个字符作为中心时- 先撤销当前字符在右侧的贡献因为它现在变成中心了- 枚举所有可能的 x y 组合0-9累加 pre2[x][y] * suf2[x][y] 到答案- 再将当前字符加入左侧的统计中3. 维护左侧- pre[d]当前左侧数字 d 出现的次数- pre2[d][j]当前左侧能形成的以 d 开头、j 结尾的两位数子序列数量JavaScript 代码/*** param {string} s* return {number}*/var countPalindromes function(s) {const MOD 1e9 7;const n s.length;// 右侧统计const suf new Array(10).fill(0);const suf2 Array.from({ length: 10 }, () new Array(10).fill(0));// 先预处理右侧for (let i n - 1; i 0; i--) {const d parseInt(s[i]);for (let j 0; j 10; j) {suf2[d][j] suf[j];}suf[d];}// 左侧统计const pre new Array(10).fill(0);const pre2 Array.from({ length: 10 }, () new Array(10).fill(0));let ans 0;for (let i 0; i n; i) {const d parseInt(s[i]);// 当前字符作为中心从右侧移除suf[d]--;for (let j 0; j 10; j) {suf2[d][j] - suf[j];}// 枚举所有可能的 xy 组合for (let x 0; x 10; x) {for (let y 0; y 10; y) {ans (ans pre2[x][y] * suf2[x][y]) % MOD;}}// 当前字符加入左侧for (let j 0; j 10; j) {pre2[d][j] pre[j];}pre[d];}return ans;};复杂度分析- 时间复杂度O(n × 10²) O(100n)其中 n 是字符串长度。因为每次枚举所有两位组合100种但实际可以通过维护 cur 变量优化到 O(10n)- 空间复杂度O(10²) O(100)常数空间优化版本O(10n)如果追求更优的性能可以维护一个 cur 变量来避免每次枚举100种组合var countPalindromes function(s) {const MOD 1e9 7;const n s.length;const suf new Array(10).fill(0);const suf2 Array.from({ length: 10 }, () new Array(10).fill(0));for (let i n - 1; i 0; i--) {const d parseInt(s[i]);for (let j 0; j 10; j) {suf2[d][j] suf[j];}suf[d];}const pre new Array(10).fill(0);const pre2 Array.from({ length: 10 }, () new Array(10).fill(0));let ans 0;let cur 0; // 当前中心位置能贡献的回文数for (let i 0; i n; i) {const d parseInt(s[i]);// 从右侧移除当前字符suf[d]--;for (let j 0; j 10; j) {cur - pre2[d][j] * suf[j]; // 减去受影响的组合suf2[d][j] - suf[j];}ans (ans cur) % MOD;// 加入左侧for (let j 0; j 10; j) {cur pre[j] * suf2[d][j]; // 加上新增的组合pre2[d][j] pre[j];}pre[d];}return ans;};这样每次只更新与当前数字 d 相关的10种组合而不是全部100种效率更高。
