LeetCode 139「单词拆分」的 Rust 实现。提供动态规划（推荐）和记忆化 DFS 两种写法。
思路：动态规划
定义 dp[i] 表示字符串 s 的前 i 个字符（即 s[0…i]）能否被拆分成字典中的单词。
· 初始状态：dp[0] = true，空字符串默认可拆分。
· 状态转移：对每个位置 i，枚举分割点 j（0 ≤ 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:Vec<String>)->bool{// 将字典转为 HashSet<&str>，借用 word_dict 中的字符串letword_set:HashSet<&str>=word_dict.iter().map(|w|w.as_str()).collect();letn=s.len();letmutdp=vec![false;n+1];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])：HashSet<&str> 的 contains 可直接接收 &str，因 &str: Borrow。
补充：记忆化 DFS
usestd::collections::{HashMap,HashSet};implSolution{pubfnword_break(s:String,word_dict:Vec<String>)->bool{letword_set:HashSet<String>=word_dict.into_iter().collect();letmutmemo:HashMap<usize,bool>=HashMap::new();fndfs(start:usize,s:&str,word_set:&HashSet<String>,memo:&mutHashMap<usize,bool>,)->bool{ifstart==s.len(){returntrue;}ifletSome(&res)=memo.get(&start){returnres;}forendinstart+1..=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()。
