LeetCode 139「单词拆分」的 Rust 实现。提供动态规划推荐和记忆化 DFS 两种写法。思路动态规划定义 dp[i] 表示字符串 s 的前 i 个字符即 s[0…i]能否被拆分成字典中的单词。· 初始状态dp[0] true空字符串默认可拆分。· 状态转移对每个位置 i枚举分割点 j0 ≤ j i若 dp[j] true 且 s[j…i] 在字典中则 dp[i] true。· 最终答案dp[n]其中 n s.len()。用 HashSet 存储字典实现 O(1) 的查找。Rust 实现动态规划usestd::collections::HashSet;implSolution{pubfnword_break(s:String,word_dict:VecString)-bool{// 将字典转为 HashSetstr借用 word_dict 中的字符串letword_set:HashSetstrword_dict.iter().map(|w|w.as_str()).collect();letns.len();letmutdpvec![false;n1];dp[0]true;foriin1..n{forjin0..i{ifdp[j]word_set.contains(s[j..i]){dp[i]true;break;}}}dp[n]}}说明· s[j…i] 是字符串切片由于题目限定小写字母ASCII字节索引即字符索引安全。· word_set.contains(s[j…i])HashSetstr 的 contains 可直接接收 str因 str: Borrow。补充记忆化 DFSusestd::collections::{HashMap,HashSet};implSolution{pubfnword_break(s:String,word_dict:VecString)-bool{letword_set:HashSetStringword_dict.into_iter().collect();letmutmemo:HashMapusize,boolHashMap::new();fndfs(start:usize,s:str,word_set:HashSetString,memo:mutHashMapusize,bool,)-bool{ifstarts.len(){returntrue;}ifletSome(res)memo.get(start){returnres;}forendinstart1..s.len(){ifword_set.contains(s[start..end])dfs(end,s,word_set,memo){memo.insert(start,true);returntrue;}}memo.insert(start,false);false}dfs(0,s,word_set,mutmemo)}}两种方法均可通过。动态规划更直观DFS 记忆化在字典单词长度较短时可能更快。复杂度分析方法 时间复杂度 空间复杂度动态规划 O(n²) O(n)记忆化 DFS O(n²)最坏 O(n)其中 n s.len()。