元宝 LeetCode 131. 分割回文串 Rust实现

Rust 实现 LeetCode 131 的核心逻辑和 Python 完全一致依然是回溯Backtracking。不过在 Rust 里需要稍微注意字符串处理和递归函数的写法。方法一回溯 实时回文判断最直观面试首选ACRust 的“String” 是 UTF-8 编码按索引切片不太方便但本题输入保证是小写英文字母所以可以直接用“as_bytes()” 转成字节切片来处理回文判断用双指针更高效。impl Solution {pub fn partition(s: String) - VecVec {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 VecVec,) {// 切到末尾说明找到了一种合法分割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) - VecVec {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 VecVec,) {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:end1]”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 实现那题求最少分割次数从回溯直接升级到动态规划是这道题目的经典进阶。