Kimi LeetCode 3563. 移除相邻字符后字典序最小的字符串 TypeScript实现
以下是 LeetCode 3563 移除相邻字符后字典序最小的字符串 的 TypeScript 实现。
核心思路
与 Rust 实现相同的区间 DP 策略，利用一个二维 DP 表同时解决「能否删空」和「最小字典序」两个问题：
- `dp[i][j]` 表示子串 `s[i..j)`（左闭右开区间）经过若干次操作后能得到的字典序最小字符串。
- 若 `dp[i+1][k] === ""`，说明 `s[i+1..k]` 可被完全删空，此时 `s[i]` 与 `s[k]` 变为相邻。若它们还是循环字母表中的连续字符（如 `'a'` 与 `'z'`），则二者可一并删除，结果为 `dp[k+1][j]`。
- 对每个区间，要么保留 `s[i]`，要么尝试删除 `s[i]`，取字典序最小者。
时间复杂度 O(n^3)，空间复杂度 O(n^2)，对于 n \le 250 完全可接受。
```typescript
function 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[i+1..k] 能完全删空（dp[i+1][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"`，保留 `"a"`
`"bcda"` `""` 删除 `"cd"` 得 `"ba"`，再删除 `"ba"` 得空串
`"zdce"` `"zdce"` 删除 `"dc"` 得 `"ze"`，但 `"zdce"` 字典序比 `"ze"` 更小，故不删
`"az"` `""` `'a'` 与 `'z'` 循环相邻，可直接删除