Kimi k2.6 LeetCode 2983. 回文串重新排列查询 TypeScript实现
以下是 LeetCode 2983. 回文串重新排列查询 的 TypeScript 实现,核心思路与 Java 版本一致。
TypeScript 代码
```typescript
function canMakePalindromeQueries(s: string, queries: number[][]): boolean[] {
const n = s.length;
const m = n / 2;
// 左半部分
const left = s.substring(0, m);
// 右半部分反转
const rightReversed = s.substring(m).split('').reverse().join('');
// 前缀和数组
const pre1: number[][] = Array.from({ length: m + 1 }, () => new Array(26).fill(0));
const pre2: number[][] = Array.from({ length: m + 1 }, () => new Array(26).fill(0));
// diff[i] = 前 i 个位置中,left[j] !== rightReversed[j] 的个数
const diff: number[] = new Array(m + 1).fill(0);
for (let i = 1; i <= m; i++) {
// 复制前一个状态
for (let j = 0; j < 26; j++) {
pre1[i][j] = pre1[i - 1][j];
pre2[i][j] = pre2[i - 1][j];
}
// 更新当前字符计数
pre1[i][left.charCodeAt(i - 1) - 97]++;
pre2[i][rightReversed.charCodeAt(i - 1) - 97]++;
// 更新不匹配计数
diff[i] = diff[i - 1] + (left[i - 1] === rightReversed[i - 1] ? 0 : 1);
}
const ans: boolean[] = new Array(queries.length);
for (let i = 0; i < queries.length; i++) {
const [a, b, c, d] = queries[i];
// 将右半部分的查询映射到反转后的坐标
const c2 = n - 1 - d;
const d2 = n - 1 - c;
if (a <= c2) {
ans[i] = check(pre1, pre2, diff, a, b, c2, d2);
} else {
ans[i] = check(pre2, pre1, diff, c2, d2, a, b);
}
}
return ans;
function check(
pre1: number[][],
pre2: number[][],
diff: number[],
a: number,
b: number,
c: number,
d: number
): boolean {
// 不可变区域必须已经匹配
if (diff[a] > 0 || diff[diff.length - 1] - diff[Math.max(b, d) + 1] > 0) {
return false;
}
// 情况1:包含关系
if (d <= b) {
return arraysEqual(count(pre1, a, b), count(pre2, a, b));
}
// 情况2:不相交
if (b < c) {
return diff[c] - diff[b + 1] === 0
&& arraysEqual(count(pre1, a, b), count(pre2, a, b))
&& arraysEqual(count(pre1, c, d), count(pre2, c, d));
}
// 情况3:相交但不包含
const cnt1 = sub(count(pre1, a, b), count(pre2, a, c - 1));
const cnt2 = sub(count(pre2, c, d), count(pre1, b + 1, d));
return cnt1 !== null && cnt2 !== null && arraysEqual(cnt1, cnt2);
}
function count(pre: number[][], l: number, r: number): number[] {
const res = new Array(26).fill(0);
for (let i = 0; i < 26; i++) {
res[i] = pre[r + 1][i] - pre[l][i];
}
return res;
}
function sub(a: number[], b: number[]): number[] | null {
const res = new Array(26).fill(0);
for (let i = 0; i < 26; i++) {
res[i] = a[i] - b[i];
if (res[i] < 0) return null;
}
return res;
}
function arraysEqual(a: number[], b: number[]): boolean {
for (let i = 0; i < 26; i++) {
if (a[i] !== b[i]) return false;
}
return true;
}
}
```
核心逻辑说明
步骤 说明
字符串拆分 `left = s[0..m-1]`,`rightReversed = s[n-1..m]`(反转右半)
坐标映射 右半查询 `[c,d]` 映射为反转后坐标:`c' = n-1-d`,`d' = n-1-c`
不可变区域检查 查询区间外的位置必须已经对称匹配(`diff` 前缀和判断)
三种区间关系 包含、不相交、相交但不包含,分别用字符频次比较处理
复杂度
- 时间:O((n + q) \times |\Sigma|),|\Sigma| = 26
- 空间:O(n \times |\Sigma|)
更多推荐



所有评论(0)