leetcode

longest_common_prefix.rs (6280B)

---

 //! Write a function to find the longest common prefix string amongst
 //! an array of strings.
 //!
 //! If there is no common prefix, return an empty string "".
 
 use std::collections::{BTreeMap, HashMap, HashSet};
 
 use tracing::info;
 
 // First manual attempt - the ugliest solution that worked
 // 255ms, 2.40mb
 fn solution_1(words: Vec<String>) -> String {
     let mut prefixes = HashMap::<usize, char>::new();
     let mut matches = Vec::<(usize, char)>::new();
 
     let mut final_results = Vec::<(usize, char)>::new();
 
     for word in words.iter() {
         info!("{word}");
         for (idx, char) in word.chars().enumerate() {
             info!("{idx}: {char}");
             prefixes.insert(idx, char);
         }
     }
 
     for word in words.iter() {
         for (index, prefix) in prefixes.clone() {
             let mut current = word.char_indices();
             let result = current.find(|(idx, char)| idx.eq(&index) && char.eq(&prefix));
             if let Some(found) = result {
                 info!("Match found: {index}: {prefix}: {found:?}");
                 matches.push((index, prefix));
             } else {
                 info!("No match found");
             }
         }
     }
 
     for char in matches.iter() {
         let count = matches.iter().filter(|x| x.eq(&char)).count();
 
         if count.eq(&words.len()) && !final_results.contains(char) {
             final_results.push(*char);
         }
     }
 
     final_results.sort_by_key(|x| x.0);
 
     info!("Final results: {final_results:?}");
 
     let mut prev: usize = 0;
     final_results.retain(|(index, _)| {
         if index.eq(&0) {
             return true;
         }
         if index.eq(&(prev + 1)) {
             prev = *index;
             true
         } else {
             false
         }
     });
 
     info!("Retained results: {final_results:?}");
 
     let has_zero = final_results.iter().any(|(idx, _)| idx.eq(&0));
     if !has_zero {
         return String::new();
     }
 
     let result = String::from_iter(final_results.iter().map(|x| x.1));
     info!("Result: {result}\n\n");
     result
 }
 
 // Second try
 // 115ms, 2.41mb
 fn solution_2(strs: Vec<String>) -> String {
     let mut common = Vec::<(usize, char)>::new();
 
     let characters = strs
         .iter()
         .flat_map(|x| x.char_indices())
         .collect::<Vec<(usize, char)>>();
     info!("characters: {characters:?}");
 
     for (index, character) in characters {
         info!("Index: {index} - Character: {character}");
         let prefix = String::from_iter(common.iter().map(|x| x.1));
         let all_starts_with = strs
             .iter()
             .all(|x| x.starts_with(&format!("{prefix}{character}")));
         info!("Does all words starts with {prefix}? {all_starts_with}");
         let contains = strs.iter().all(|x| x.contains(character));
         if contains && all_starts_with {
             if common.is_empty() && index.eq(&0) {
                 common.push((index, character));
             } else {
                 if let Some(last) = common.last() {
                     info!("previous: {last:?}");
                     if last.0 + 1 == index {
                         common.push((index, character));
                     }
                 }
             }
         }
     }
 
     info!("Common: {common:?}");
     let prefix = String::from_iter(common.iter().map(|x| x.1));
     info!("PREFIX: {prefix}");
     prefix
 }
 
 // Third try: BTreeMap is automatically sorted
 // 0ms, 2.33mb
 fn solution_3(strs: Vec<String>) -> String {
     let mut common = Vec::<char>::new();
 
     for (index, character) in strs
         .iter()
         .flat_map(|x| x.char_indices())
         .collect::<BTreeMap<usize, char>>()
     {
         info!("{index}: {character}");
         let existing_prefix = String::from_iter(&common);
         let prefix = format!("{existing_prefix}{character}");
         if strs.iter().all(|x| x.starts_with(&prefix)) {
             common.push(character);
         }
     }
 
     info!("Common: {common:?}");
 
     String::from_iter(common)
 }
 
 // Fourth try:
 // Can we use less than 2.1mb memory?
 fn solution_4(strs: Vec<String>) -> String {
     String::new()
 }
 
 #[cfg(test)]
 mod tests {
     use crate::{
         array::longest_common_prefix::{solution_1, solution_2, solution_3, solution_4},
         test_utils::benchmark::init_benchmark_tracing,
     };
 
     struct Case {
         input: Vec<String>,
         output: String,
     }
 
     fn full_cases() -> Vec<Case> {
         vec![
             Case {
                 input: vec![
                     "flower".to_string(),
                     "flow".to_string(),
                     "flight".to_string(),
                 ],
                 output: "fl".to_string(),
             },
             Case {
                 input: vec!["dog".to_string(), "racecar".to_string(), "car".to_string()],
                 output: String::new(),
             },
             Case {
                 input: vec!["cir".to_string(), "car".to_string()],
                 output: "c".to_string(),
             },
             Case {
                 input: vec!["babb".to_string(), "caa".to_string()],
                 output: String::new(),
             },
             Case {
                 input: vec![
                     "reflower".to_string(),
                     "flow".to_string(),
                     "flight".to_string(),
                 ],
                 output: String::new(),
             },
             Case {
                 input: vec!["aa".to_string(), "aa".to_string()],
                 output: "aa".to_string(),
             },
             Case {
                 input: vec!["aa".to_string(), "ab".to_string()],
                 output: "a".to_string(),
             },
         ]
     }
 
     fn run_solver_cases(solver: fn(Vec<String>) -> String, cases: Vec<Case>) {
         init_benchmark_tracing();
         for case in cases {
             assert_eq!(solver(case.input), case.output);
         }
     }
 
     // #[test]
     // fn solver_1() {
     //     run_solver_cases(solution_1, full_cases());
     // }
 
     // #[test]
     // fn solver_2() {
     //     run_solver_cases(solution_2, full_cases());
     // }
 
     #[test]
     fn solver_3() {
         run_solver_cases(solution_3, full_cases());
     }
 
     #[test]
     fn solver_4() {
         run_solver_cases(solution_4, full_cases());
     }
 }