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

以下是 LeetCode 3563 移除相邻字符后字典序最小的字符串 的 Rust 实现。核心思路这道题使用区间 DP 巧妙地将「能否删空」和「最小字典序」两个子问题合并到一个 DP 表中- dp[i][j] 表示子串 s[i..j)左闭右开经过若干次操作后能得到的字典序最小的字符串。- 如果 dp[i1][k] 说明 s[i1..k] 可以被完全删空此时 s[i] 和 s[k] 会变为相邻。若它们还是字母表中的连续字符包括循环连续 a 与 z则 s[i] 和 s[k] 也可以一并删除结果为 dp[k1][j]。- 对每个区间要么保留 s[i]要么尝试删除 s[i]取字典序最小者。时间复杂度 O(n^3)空间复杂度 O(n^2)对于 n \le 250 完全可接受。rustimpl 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: VecVecString 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[i1..k] 能完全删空dp[i1][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保留 abcda 删除 cd 得 ba再删除 ba 得空串zdce zdce 删除 dc 得 ze但 zdce 字典序比 ze 更小故不删az a 与 z 循环相邻可直接删除