I wrote an answer to a leetcode question(https://leetcode.com/problems/longest-common-prefix/) using the divide and conquer algorithm(https://www.geeksforgeeks.org/longest-common-prefix-using-divide-and-conquer-algorithm/)
Here is my solution: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=ec9500b58112e91d7ccdcf40c2aa6d39
Leetcode says it is faster than only 30% of the solutions. How can I make it more efficient?
#Implementation of the Divide and Conquer algorithm is slow
onyx nexus
obtuse coral
It's probably from allocating all the time. Leetcode is bad for this (for example, this function should take &[String] instead of Vec<String> and return &str instead of String). You can make this entire function without allocating.
It will also speed up a little more by doing it iteratively instead of recursively. And then more by using bytes instead of chars, but that's also not very rust-like.
?eval
fn main() {
let s = ["flower", "flow", "flight"];
let s = s
.into_iter()
.map(|s| s.to_string())
.collect::<Vec<String>>();
dbg!(longest_common_prefix(s));
}
fn divide_and_conquer(v: &[String]) -> &str {
match v.len() {
1 => &v[0],
2 => common_prefix(&v[0], &v[1]),
_ => common_prefix(divide_and_conquer(&v[0..=1]), divide_and_conquer(&v[2..])),
}
}
fn common_prefix<'a>(s1: &'a str, s2: &str) -> &'a str {
for (i, (c1, c2)) in s1.chars().zip(s2.chars()).enumerate() {
if c1 != c2 {
return &s1[0..i]
}
}
let len = s1.len().min(s2.len());
&s1[0..len]
}
pub fn longest_common_prefix(strs: Vec<String>) -> String {
longest_common_prefix_ref(&strs).to_string()
}
fn longest_common_prefix_ref(strs: &[String]) -> &str {
divide_and_conquer(&strs)
}
unkempt dustBOT
Running `target/debug/playground`
[src/main.rs:7] longest_common_prefix(s) = "fl"
So the traditional way of iterating character by character would've been better altogether.