Rust 实现 LeetCode 131 的核心逻辑和 Python 完全一致，依然是回溯（Backtracking）。不过在 Rust 里需要稍微注意字符串处理和递归函数的写法。
方法一：回溯 + 实时回文判断（最直观，面试首选）AC
Rust 的
“String” 是 UTF-8 编码，按索引切片不太方便，但本题输入保证是小写英文字母，所以可以直接用
“as_bytes()” 转成字节切片来处理，回文判断用双指针更高效。
impl Solution {
pub fn partition(s: String) -> Vec<Vec> {
let bytes = s.as_bytes();
let mut res = Vec::new();
let mut path = Vec::new();
backtrack(0, bytes, &mut path, &mut res);
res
}
}
fn backtrack(
start: usize,
bytes: &[u8],
path: &mut Vec,
res: &mut Vec<Vec>,
) {
// 切到末尾，说明找到了一种合法分割
if start == bytes.len() {
res.push(path.clone()); // 注意：必须 clone，不能直接移走
return;
}
// 枚举当前起点能切出的所有子串 for end in start..bytes.len() { if is_palindrome(&bytes[start..=end]) { // 转成 String 加入路径 let sub = String::from_utf8(bytes[start..=end].to_vec()).unwrap(); path.push(sub); // 做选择 backtrack(end + 1, bytes, path, res); // 递归切后面的 path.pop(); // 撤销选择（回溯） } }}
fn is_palindrome(bytes: &[u8]) -> bool {
let (mut i, mut j) = (0, bytes.len().saturating_sub(1));
while i < j {
if bytes[i] != bytes[j] {
return false;
}
i += 1;
if j > 0 {
j -= 1;
} else {
break;
}
}
true
}
方法二：回溯 + DP 预处理回文表（性能更优）
如果字符串较长，频繁切片判断回文会有开销。可以先 DP 预处理所有子串的回文状态，回溯时 O(1) 查询。
impl Solution {
pub fn partition(s: String) -> Vec<Vec> {
let bytes = s.as_bytes();
let n = bytes.len();
// 1. 预处理：dp[i][j] 表示 bytes[i..=j] 是否为回文 let mut dp = vec![vec![false; n]; n]; for i in 0..n { for j in i..n { if bytes[i] == bytes[j] && (j - i <= 2 || dp[i + 1][j - 1]) { dp[i][j] = true; } } } // 2. 回溯 let mut res = Vec::new(); let mut path = Vec::new(); backtrack(0, bytes, &dp, &mut path, &mut res); res }}
fn backtrack(
start: usize,
bytes: &[u8],
dp: &[Vec],
path: &mut Vec,
res: &mut Vec<Vec>,
) {
if start == bytes.len() {
res.push(path.clone());
return;
}
for end in start..bytes.len() { if dp[start][end] { let sub = String::from_utf8(bytes[start..=end].to_vec()).unwrap(); path.push(sub); backtrack(end + 1, bytes, dp, path, res); path.pop(); } }}
Rust 版特有注意事项（面试常问）
要点 说明
“path.clone()”
“res.push(path)” 会移动所有权导致后续无法回溯，必须
“clone”，和 Python 里
“path[:]” 一个道理
字符串转换
“&[u8]” 转
“String” 用
“String::from_utf8(…).unwrap()”，本题输入安全不会 panic
递归函数位置 Rust 闭包不能递归调用自己，所以写成独立的
“fn backtrack”（或放在
“impl” 里作为辅助方法）
切片索引
“bytes[start…=end]” 是闭区间，对应
“s[start:end+1]”（Python 风格）
“saturating_sub” 回文判断里
“j = bytes.len() - 1” 在空切片时会溢出，用
“saturating_sub(1)” 更安全（虽然本题
“n >= 1”）
复杂度分析
和 Python 版一致：
- 时间复杂度：最坏
“O(2ⁿ · n)”（全
“‘a’” 字符串，每种切法都合法，拷贝路径耗时
“O(n)”） - 空间复杂度：
“O(n)” 递归栈深度（不计结果存储）；DP 版额外
“O(n²)” 存储回文表
跑个示例
let s = “aab”.to_string();
let res = Solution::partition(s);
// res = [[“a”,“a”,“b”], [“aa”,“b”]]
要不要我顺便给你写一下 LeetCode 132（分割回文串 II） 的 Rust DP 实现？那题求最少分割次数，从回溯直接升级到动态规划，是这道题目的经典进阶。
