# Go4Fun - Functional programming and more # Rust Interview Puzzles: Find the longest common prefix

### 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 `vec` Output `["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, |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` 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, vec)` which is the common prefix between the first and the second string. On the second iteration, `prx = common_prefix(prx, vec)` which is the common prefix between the common prefix `prx` from the previous iteration and the third string `vec`. And so on...

The `common_prefix` function takes 2 string slices (`s1`, `s2`), then it gets the char iterator for `s1` and `zip`s 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