commit 2d8ac40efa60e54ea126eed84808a29faf9eaa1e
parent ac0e24ff74150cfb7543d1d0b6910f6464783679
Author: ling0x <ling0x@users.noreply.github.com>
Date: Sat, 25 Jul 2026 04:21:59 +0100
update
Diffstat:
3 files changed, 196 insertions(+), 145 deletions(-)
diff --git a/src/array/longest_common_prefix.rs b/src/array/longest_common_prefix.rs
@@ -1,31 +1,75 @@
+//! 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::{HashMap, HashSet};
+
use tracing::info;
-pub fn longest_common_prefix_1(strs: Vec<String>) -> String {
- let mut seen = std::collections::HashSet::<char>::new();
- let mut seen_seen = std::collections::HashSet::<char>::new();
- let mut common = Vec::<char>::new();
- let mut common_common = Vec::<char>::new();
-
- for word in strs {
- let chars = word.chars().collect::<Vec<char>>();
- for c in chars.iter() {
- let result = seen.insert(c.to_owned());
- if !result {
- common.push(c.to_owned());
+// First manual attempt - the ugliest solution that worked
+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 cc in &common {
- let result = seen_seen.insert(cc.to_owned());
- if !result {
- common_common.push(cc.to_owned());
+ 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);
}
}
- info!("{common_common:?}");
+ 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();
+ }
- String::from_iter(common_common)
+ let result = String::from_iter(final_results.iter().map(|x| x.1));
+ info!("Result: {result}\n\n");
+ result
}
#[cfg(test)]
@@ -33,8 +77,7 @@ mod tests {
use tracing::info;
use crate::{
- array::longest_common_prefix::longest_common_prefix_1,
- test_utils::benchmark::init_benchmark_tracing,
+ array::longest_common_prefix::solution_1, test_utils::benchmark::init_benchmark_tracing,
};
struct Case {
@@ -56,6 +99,14 @@ mod tests {
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(),
+ },
]
}
@@ -68,7 +119,7 @@ mod tests {
}
#[test]
- fn longest_common_prefix_1_cases() {
- run_solver_cases("solver 1", longest_common_prefix_1, full_cases());
+ fn longest_2_cases() {
+ run_solver_cases("solver 1", solution_1, full_cases());
}
}
diff --git a/src/hash_table/two_sum.rs b/src/hash_table/two_sum.rs
@@ -1,3 +1,11 @@
+//! Given an array of integers nums and an integer target, return indices
+//! of the two numbers such that they add up to target.
+//!
+//! You may assume that each input would have exactly one solution, and
+//! you may not use the same element twice.
+//!
+//! You can return the answer in any order.
+
// First try - brute force approach without optimization
// 101ms, 2.37MB
pub fn two_sum_1(nums: Vec<i32>, target: i32) -> Vec<i32> {
@@ -185,117 +193,117 @@ pub fn two_sum_9(nums: Vec<i32>, target: i32) -> Vec<i32> {
Vec::new()
}
-#[cfg(test)]
-mod tests {
- use crate::hash_table::two_sum::{
- two_sum_1, two_sum_2, two_sum_3, two_sum_4, two_sum_5, two_sum_6, two_sum_7, two_sum_8,
- two_sum_9,
- };
- use crate::test_utils::benchmark::{init_benchmark_tracing, run_and_assert_vec_any_order};
-
- #[derive(Clone)]
- struct TwoSumCase {
- name: &'static str,
- nums: Vec<i32>,
- target: i32,
- expected: Vec<i32>,
- }
-
- fn full_cases() -> Vec<TwoSumCase> {
- vec![
- TwoSumCase {
- name: "case_1",
- nums: vec![2, 7, 11, 15],
- target: 9,
- expected: vec![0, 1],
- },
- TwoSumCase {
- name: "case_2",
- nums: vec![3, 2, 3],
- target: 6,
- expected: vec![0, 2],
- },
- TwoSumCase {
- name: "case_3",
- nums: vec![3, 2, 4],
- target: 6,
- expected: vec![1, 2],
- },
- TwoSumCase {
- name: "case_4",
- nums: vec![-3, 4, 3, 90],
- target: 0,
- expected: vec![0, 2],
- },
- ]
- }
-
- fn run_solver_cases(
- solver_name: &str,
- solver: fn(Vec<i32>, i32) -> Vec<i32>,
- cases: Vec<TwoSumCase>,
- ) {
- init_benchmark_tracing();
- for case in cases {
- run_and_assert_vec_any_order(
- &format!("{solver_name}_{}", case.name),
- case.expected,
- || solver(case.nums, case.target),
- );
- }
- }
-
- #[test]
- #[ignore]
- fn two_sum_1_cases() {
- run_solver_cases("two_sum_1", two_sum_1, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_2_cases() {
- run_solver_cases("two_sum_2", two_sum_2, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_3_cases() {
- run_solver_cases("two_sum_3", two_sum_3, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_4_cases() {
- run_solver_cases("two_sum_4", two_sum_4, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_5_cases() {
- run_solver_cases("two_sum_5", two_sum_5, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_6_cases() {
- run_solver_cases("two_sum_6", two_sum_6, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_7_cases() {
- run_solver_cases("two_sum_7", two_sum_7, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_8_cases() {
- run_solver_cases("two_sum_8", two_sum_8, full_cases());
- }
-
- #[test]
- #[ignore]
- fn two_sum_9_cases() {
- run_solver_cases("two_sum_9", two_sum_9, full_cases());
- }
-}
+// #[cfg(test)]
+// mod tests {
+// use crate::hash_table::two_sum::{
+// two_sum_1, two_sum_2, two_sum_3, two_sum_4, two_sum_5, two_sum_6, two_sum_7, two_sum_8,
+// two_sum_9,
+// };
+// use crate::test_utils::benchmark::{init_benchmark_tracing, run_and_assert_vec_any_order};
+
+// #[derive(Clone)]
+// struct TwoSumCase {
+// name: &'static str,
+// nums: Vec<i32>,
+// target: i32,
+// expected: Vec<i32>,
+// }
+
+// fn full_cases() -> Vec<TwoSumCase> {
+// vec![
+// TwoSumCase {
+// name: "case_1",
+// nums: vec![2, 7, 11, 15],
+// target: 9,
+// expected: vec![0, 1],
+// },
+// TwoSumCase {
+// name: "case_2",
+// nums: vec![3, 2, 3],
+// target: 6,
+// expected: vec![0, 2],
+// },
+// TwoSumCase {
+// name: "case_3",
+// nums: vec![3, 2, 4],
+// target: 6,
+// expected: vec![1, 2],
+// },
+// TwoSumCase {
+// name: "case_4",
+// nums: vec![-3, 4, 3, 90],
+// target: 0,
+// expected: vec![0, 2],
+// },
+// ]
+// }
+
+// fn run_solver_cases(
+// solver_name: &str,
+// solver: fn(Vec<i32>, i32) -> Vec<i32>,
+// cases: Vec<TwoSumCase>,
+// ) {
+// init_benchmark_tracing();
+// for case in cases {
+// run_and_assert_vec_any_order(
+// &format!("{solver_name}_{}", case.name),
+// case.expected,
+// || solver(case.nums, case.target),
+// );
+// }
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_1_cases() {
+// run_solver_cases("two_sum_1", two_sum_1, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_2_cases() {
+// run_solver_cases("two_sum_2", two_sum_2, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_3_cases() {
+// run_solver_cases("two_sum_3", two_sum_3, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_4_cases() {
+// run_solver_cases("two_sum_4", two_sum_4, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_5_cases() {
+// run_solver_cases("two_sum_5", two_sum_5, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_6_cases() {
+// run_solver_cases("two_sum_6", two_sum_6, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_7_cases() {
+// run_solver_cases("two_sum_7", two_sum_7, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_8_cases() {
+// run_solver_cases("two_sum_8", two_sum_8, full_cases());
+// }
+
+// #[test]
+// #[ignore]
+// fn two_sum_9_cases() {
+// run_solver_cases("two_sum_9", two_sum_9, full_cases());
+// }
+// }
diff --git a/src/main.rs b/src/main.rs
@@ -1,15 +1,7 @@
-use leetcode::{
- array::longest_common_prefix::longest_common_prefix_1, hash_table::two_sum::two_sum_9,
-};
use tracing::info;
use tracing_subscriber::fmt;
fn main() {
fmt().with_target(false).compact().init();
- info!("-----------------------");
- longest_common_prefix_1(vec![
- "flower".to_string(),
- "flow".to_string(),
- "flight".to_string(),
- ]);
+ info!("Run `cargo test` to test cases");
}
