Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Rust

Answer 1

use std::collections::HashSet;

fn word_break(s: &str, dict: &HashSet<&str>) -> bool {
    let slen = s.len();
    let mut result = vec![false; slen + 1];
    result[0] = true; // empty string is always segmentable

    for i in 1..=slen {
        for j in 0..i {
            if result[j] && dict.contains(&s[j..i]) {
                result[i] = true;
                break;
            }
        }
    }

    result[slen]
}

fn main() {
    let dict: HashSet<&str> = [
        "future", "depends", "the", "on", "your", "dreams", "start", "today",
    ]
    .iter()
    .cloned()
    .collect();

    let s = "futuredependsonyourdreams";

    if word_break(s, &dict) {
        println!("The string can be segmented");
    } else {
        println!("The string cannot be segmented");
    }
}



/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

fn is_in_dict(word: &str, dict: &[&str]) -> bool {
    dict.iter().any(|&w| w == word)
}

fn word_break(str: &str, result: String, dict: &[&str]) {
    let strsize = str.len();
    for i in 1..=strsize {
        let sub_str = &str[..i];
        if is_in_dict(sub_str, dict) {
            if i == strsize {
                println!("{}{}", result, sub_str);
                return;
            }
            word_break(&str[i..], format!("{}{} ", result, sub_str), dict);
        }
    }
}

fn main() {
    let str = "butterflyplaybasketballwithbags";
    let dict = [
        "butterfly", "basketball", "bagpiper", "and", "play",
        "with", "butter", "fly", "basket", "ball", "bags",
    ];

    word_break(str, String::new(), &dict);
}



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals