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[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).