go4fun.fun
Go4Fun - Functional programming and more

Follow

Go4Fun - Functional programming and more

Follow
Rust Interview Puzzles: Find the longest common prefix

Rust Interview Puzzles: Find the longest common prefix

go4fun.fun's photo
go4fun.fun
·Dec 20, 2022·

2 min read

Problem

In a provided vector of strings vec we need to find the longest string prefix shared by all strings in the vector.

Examples:

Input vecOutput
["abcd", "abcdef", "abc", "abcde"]"abc"
["a", "abc", "ab"]"a"
["def"]"def"
["abc", "defg", "hij"]""

Solution

fn find_longest_common_prefix_string<'a>(vec: &Vec<&'a str>) -> &'a str {

    fn common_prefix<'a>(s1: &'a str, s2: &'a str) -> &'a str {
        let prefix_end_index = s1
            .chars()
            .zip(s2.chars())
            .enumerate()
            .find(|(_, (char1, char2))| char1 != char2)
            .map(|(index, _)| index)
            .unwrap_or(usize::min(s1.len(), s2.len()));
        &s1[0..prefix_end_index]
    }

    if vec.is_empty() {
        return "";
    }

    (1..vec.len()).fold(vec[0], |prx, i| common_prefix(prx, vec[i]))
}

Explanation

One way to solve the puzzle is to go through the vector of strings vec and on each iteration find the common_prefix between the common prefix prx saved so far and the current string vec[i]. The accumulating function fold is a good fit here: we provide it with the initial seed (which is the first string vec[0] in the vector) and a closure calling common_prefix function for the accumulator prx and the current string vec[i]. On the first iteration, prx = common_prefix(vec[0], vec[1]) which is the common prefix between the first and the second string. On the second iteration, prx = common_prefix(prx, vec[2]) which is the common prefix between the common prefix prx from the previous iteration and the third string vec[2]. And so on...

The common_prefix function takes 2 string slices (s1, s2), then it gets the char iterator for s1 and zips it with the char iterator for s2 (so that we can iterate over the both strings at the same time until we reach the end for one of them). Then we find the first index where char1 != char2 - that would be the end index of the common prefix.

Complexity

The worst-case time complexity of this solution is O(s) (where s is the sum of all characters of all strings). The auxiliary space complexity is O(1).


Rust Playground with this code

 
Share this