Question

How to find the longest shared prefix among all words in a string with Rust

Answer 1

use regex::Regex;
use std::collections::HashMap;

// Extract alphabetic words (lowercased)
fn extract_words(text: &str) -> Vec<String> {
    let re = Regex::new(r"[A-Za-z]+").unwrap();
    re.find_iter(text)
        .map(|m| m.as_str().to_lowercase())
        .collect()
}

// Build prefix → list of words that share that prefix
fn group_by_prefixes(words: &[String]) -> HashMap<String, Vec<String>> {
    let mut groups: HashMap<String, Vec<String>> = HashMap::new();

    for w in words {
        for i in 1..=w.len() {
            let prefix = w[..i].to_string();
            groups.entry(prefix).or_default().push(w.clone());
        }
    }

    groups
}

// Find the longest prefix that appears in 2+ words
fn longest_shared_prefix(groups: &HashMap<String, Vec<String>>) -> Option<String> {
    let mut best: Option<String> = None;

    for (prefix, list) in groups {
        if list.len() >= 2 {
            match &best {
                Some(b) if prefix.len() <= b.len() => {}
                _ => best = Some(prefix.clone()),
            }
        }
    }

    best
}

fn main() {
    let text = "The Lowly inhabitants of the lowland were surprised to see \
                the lower branches of the trees.";

    let words = extract_words(text);
    let groups = group_by_prefixes(&words);
    let prefix = longest_shared_prefix(&groups);

    if let Some(p) = prefix {
        let group = &groups[&p];
        println!("Longest shared prefix:");
        println!(
            "{} | prefix_len={} | group_count={} | {:?}",
            p,
            p.len(),
            group.len(),
            group
        );
    } else {
        println!("No shared prefix found.");
    }
}




/*
run:

Longest shared prefix:
lowl | prefix_len=4 | group_count=2 | ["lowly", "lowland"]

*/

 

70+ SQL courses for beginners and professionals