leetcode

commit 73874e5eb74637d49baec2b0402acc0706bfa5ec
parent eda3ed7516ede4a3f798261e523ac0f2b8de916e
Author: ling0x <ling0x@users.noreply.github.com>
Date:   Sun, 26 Jul 2026 17:04:38 +0100

update

Diffstat:
M
src/array/longest_common_prefix.rs
 | 
44
++++++++++++++++++++++++++++++++++++--------

1 file changed, 36 insertions(+), 8 deletions(-)
diff --git a/src/array/longest_common_prefix.rs b/src/array/longest_common_prefix.rs
@@ -3,7 +3,7 @@
 //!
 //! If there is no common prefix, return an empty string "".
 
-use std::collections::{HashMap, HashSet};
+use std::collections::{BTreeMap, HashMap, HashSet};
 
 use tracing::info;
 
@@ -112,10 +112,33 @@ fn solution_2(strs: Vec<String>) -> String {
     prefix
 }
 
+// Third try: BTreeMap is automatically sorted
+// 0ms, 2.33mb
+fn solution_3(strs: Vec<String>) -> String {
+    let mut common = Vec::<(usize, 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.iter().map(|(_, char)| char));
+        let prefix = format!("{existing_prefix}{character}");
+        if strs.iter().all(|x| x.starts_with(&prefix)) {
+            common.push((index, character));
+        }
+    }
+
+    info!("Common: {common:?}");
+
+    String::from_iter(common.iter().map(|(_, char)| char))
+}
+
 #[cfg(test)]
 mod tests {
     use crate::{
-        array::longest_common_prefix::{solution_1, solution_2},
+        array::longest_common_prefix::{solution_1, solution_2, solution_3},
         test_utils::benchmark::init_benchmark_tracing,
     };
 
@@ -172,13 +195,18 @@ mod tests {
         }
     }
 
-    #[test]
-    fn solver_1() {
-        run_solver_cases(solution_1, full_cases());
-    }
+    // #[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_2() {
-        run_solver_cases(solution_2, full_cases());
+    fn solver_3() {
+        run_solver_cases(solution_3, full_cases());
     }
 }