leetcode

commit eda3ed7516ede4a3f798261e523ac0f2b8de916e
parent 2d8ac40efa60e54ea126eed84808a29faf9eaa1e
Author: ling0x <ling0x@users.noreply.github.com>
Date:   Sun, 26 Jul 2026 02:38:50 +0100

update

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

1 file changed, 66 insertions(+), 7 deletions(-)
diff --git a/src/array/longest_common_prefix.rs b/src/array/longest_common_prefix.rs
@@ -8,6 +8,7 @@ use std::collections::{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();
@@ -72,12 +73,50 @@ fn solution_1(words: Vec<String>) -> String {
     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
+}
+
 #[cfg(test)]
 mod tests {
-    use tracing::info;
-
     use crate::{
-        array::longest_common_prefix::solution_1, test_utils::benchmark::init_benchmark_tracing,
+        array::longest_common_prefix::{solution_1, solution_2},
+        test_utils::benchmark::init_benchmark_tracing,
     };
 
     struct Case {
@@ -107,19 +146,39 @@ mod tests {
                 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_name: &str, solver: fn(Vec<String>) -> String, cases: Vec<Case>) {
+    fn run_solver_cases(solver: fn(Vec<String>) -> String, cases: Vec<Case>) {
         init_benchmark_tracing();
-        info!("{solver_name}");
         for case in cases {
             assert_eq!(solver(case.input), case.output);
         }
     }
 
     #[test]
-    fn longest_2_cases() {
-        run_solver_cases("solver 1", solution_1, full_cases());
+    fn solver_1() {
+        run_solver_cases(solution_1, full_cases());
+    }
+
+    #[test]
+    fn solver_2() {
+        run_solver_cases(solution_2, full_cases());
     }
 }