Kimi LeetCode 3563. 移除相邻字符后字典序最小的字符串 Rust实现

以下是 LeetCode 3563 移除相邻字符后字典序最小的字符串 的 Rust 实现。

核心思路

这道题使用区间 DP 巧妙地将「能否删空」和「最小字典序」两个子问题合并到一个 DP 表中：

- `dp[i][j]` 表示子串 `s[i..j)`（左闭右开）经过若干次操作后能得到的字典序最小的字符串。
- 如果 `dp[i+1][k] == ""`，说明 `s[i+1..k]` 可以被完全删空，此时 `s[i]` 和 `s[k]` 会变为相邻。若它们还是字母表中的连续字符（包括循环连续 `'a'` 与 `'z'`），则 `s[i]` 和 `s[k]` 也可以一并删除，结果为 `dp[k+1][j]`。
- 对每个区间，要么保留 `s[i]`，要么尝试删除 `s[i]`，取字典序最小者。

时间复杂度 O(n^3)，空间复杂度 O(n^2)，对于 n \le 250 完全可接受。

```rust
impl Solution {
pub fn lexicographically_smallest_string(s: String) -> String {
let n = s.len();
let s_bytes = s.as_bytes();

// dp[i][j] = 子串 s[i..j) 能得到的字典序最小字符串
let mut dp: Vec<Vec<String>> = vec![vec![String::new(); n + 1]; n + 1];

// 按区间长度从小到大填表
for d in 1..=n {
for i in 0..=n - d {
let j = i + d;

// 选项1：保留 s[i]
let mut best = String::new();
best.push(s_bytes[i] as char);
best.push_str(&dp[i + 1][j]);

// 选项2：尝试将 s[i] 与某个 s[k] 配对删除
// 要求 s[i+1..k] 能完全删空（dp[i+1][k] == ""）
// 且 s[i] 与 s[k] 在循环字母表中相邻
for k in (i + 1)..j {
if Self::is_consecutive(s_bytes[i], s_bytes[k]) && dp[i + 1][k].is_empty() {
let candidate = &dp[k + 1][j];
if candidate < &best {
best = candidate.clone();
}
}
}

dp[i][j] = best;
}
}

dp[0][n].clone()
}

// 判断两个字符在循环字母表中是否相邻
// 'a'-'b', 'b'-'a', 'a'-'z', 'z'-'a' 均视为相邻
fn is_consecutive(a: u8, b: u8) -> bool {
let diff = if a > b { a - b } else { b - a };
diff == 1 || diff == 25
}
}
```

验证示例

输入 输出 说明
`"abc"` `"a"` 删除 `"bc"`，保留 `"a"`
`"bcda"` `""` 删除 `"cd"` 得 `"ba"`，再删除 `"ba"` 得空串
`"zdce"` `"zdce"` 删除 `"dc"` 得 `"ze"`，但 `"zdce"` 字典序比 `"ze"` 更小，故不删
`"az"` `""` `'a'` 与 `'z'` 循环相邻，可直接删除