以下是 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|)

 

Logo

中国智能体开发者社区,聚焦智能体与大模型开发,提供前沿资讯、实用工具链、开源项目及行业案例。通过技术沙龙、开发者大赛等活动,促进经验交流与协作,助力开发者快速构建创新智能应用。

更多推荐