fn dict_contains(candidate: &str, dict: &[String]) -> bool {
/*
Helper: check if a substring is in the dictionary.
Uses a simple vector of strings and linear search.
*/
dict.contains(&candidate.to_string())
}
fn segment_text(text: &str, dict: &[String]) -> Vec<String> {
/*
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
*/
let n: usize = text.len();
// dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid
let mut dp: Vec<usize> = vec![0; n + 1];
let mut valid: Vec<bool> = vec![false; n + 1];
valid[0] = true; // empty prefix is valid
for i in 1..=n {
for j in 0..i {
// Check whether dp[j] contains a valid split point;
// if it does, it means the prefix text[0:j] can be segmented.
if valid[j] {
let candidate: &str = &text[j..i];
// Verify whether this substring is a valid dictionary word.
if dict_contains(candidate, dict) {
dp[i] = j;
valid[i] = true;
// Stop searching for other j values because we already found
// a valid segmentation ending at i.
break;
}
}
}
}
// If dp[n] is not valid, segmentation is impossible
if !valid[n] {
return vec![];
}
// Backtrack to recover words
let mut words: Vec<String> = Vec::new();
let mut idx: usize = n;
while idx > 0 {
let j: usize = dp[idx];
let w: String = text[j..idx].to_string();
words.push(w);
idx = j;
}
// Reverse the collected words
words.reverse();
words
}
fn main() {
let text: &str = "thisisatestfoo";
// Example dictionary
let dict: Vec<String> = vec![
"this".into(),
"is".into(),
"a".into(),
"test".into(),
"hello".into(),
"world".into(),
"foo".into(),
"bar".into(),
];
let words: Vec<String> = segment_text(text, &dict);
println!("Segmentation result:");
for w in words {
println!("{}", w);
}
}
/*
run:
Segmentation result:
this
is
a
test
foo
*/
