以下是 LeetCode 3563 移除相邻字符后字典序最小的字符串 的 TypeScript 实现。核心思路与 Rust 实现相同的区间 DP 策略利用一个二维 DP 表同时解决「能否删空」和「最小字典序」两个问题- dp[i][j] 表示子串 s[i..j)左闭右开区间经过若干次操作后能得到的字典序最小字符串。- 若 dp[i1][k] 说明 s[i1..k] 可被完全删空此时 s[i] 与 s[k] 变为相邻。若它们还是循环字母表中的连续字符如 a 与 z则二者可一并删除结果为 dp[k1][j]。- 对每个区间要么保留 s[i]要么尝试删除 s[i]取字典序最小者。时间复杂度 O(n^3)空间复杂度 O(n^2)对于 n \le 250 完全可接受。typescriptfunction lexicographicallySmallestString(s: string): string {const n s.length;const sArr s.split();// dp[i][j] 子串 s[i..j) 能得到的字典序最小字符串const dp: string[][] Array.from({ length: n 1 }, () Array(n 1).fill());// 按区间长度从小到大填表for (let d 1; d n; d) {for (let i 0; i n - d; i) {const j i d;// 选项1保留 s[i]let best sArr[i] dp[i 1][j];// 选项2尝试将 s[i] 与某个 s[k] 配对删除// 要求 s[i1..k] 能完全删空dp[i1][k] // 且 s[i] 与 s[k] 在循环字母表中相邻for (let k i 1; k j; k) {if (isConsecutive(sArr[i], sArr[k]) dp[i 1][k] ) {const candidate dp[k 1][j];if (candidate best) {best candidate;}}}dp[i][j] best;}}return dp[0][n];}// 判断两个字符在循环字母表中是否相邻// a-b, b-a, a-z, z-a 均视为相邻function isConsecutive(a: string, b: string): boolean {const codeA a.charCodeAt(0);const codeB b.charCodeAt(0);const diff Math.abs(codeA - codeB);return diff 1 || diff 25;}验证示例输入 输出 说明abc a 删除 bc保留 abcda 删除 cd 得 ba再删除 ba 得空串zdce zdce 删除 dc 得 ze但 zdce 字典序比 ze 更小故不删az a 与 z 循环相邻可直接删除