Longest common prefix (Leetcode)

Question

Link here I'm currently learning c++ coming from a python background, so I'll include a solution in python and in c++ for the problem statement below, I'm including both for convenience, if you don't know c++, feel free to review python and vice versa.

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 "".

Example 1:

Input: words = ['flower', 'flow', 'flight']

Output: 'fl'

Example 2:

Input: strs = ['dog', 'racecar', 'car']

Output: ''

longest_common_prefix.py

def get_longest(words):
 if not words:
 return ''
 common = words[0]
 for word in words:
 while not word.startswith(common):
 common = common[:-1]
 return common
if __name__ == '__main__':
 print(f"Longest prefix: \n{get_longest(['flower', 'flow', 'fly'])}")

Leetcode stats:

• Runtime: 32 ms, faster than 76.56% of Python3 online submissions for Longest Common Prefix.

• Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Longest Common Prefix.

longest_common_prefix.h

#ifndef LEETCODE_LONGEST_COMMON_PREFIX_H
#define LEETCODE_LONGEST_COMMON_PREFIX_H
#include <string_view>
#include <vector>
std::string_view get_common_prefix(const std::vector<std::string_view>& words);
#endif //LEETCODE_LONGEST_COMMON_PREFIX_H

longest_common_prefix.cpp

#include <iostream>
#include <string_view>
#include <vector>
std::string_view get_common_prefix(const std::vector<std::string_view> &words) {
 if (words.empty())
 return "";
 std::string_view common = words[0];
 for (auto word: words) {
 while (word.find(common, 0) != 0) {
 common = common.substr(0, common.size() - 1);
 }
 }
 return common;
}
int main() {
 std::vector<std::string_view> xxx{"flow", "flower", "fly"};
 std::cout << "Longest prefix:\n" << get_common_prefix(xxx);
}

Leetcode stats:

• Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Common Prefix.
• Memory Usage: 9.9 MB, less than 7.29% of C++ online submissions for Longest Common Prefix.

• user228914: I posted a question on meta taking this into consideration( 2 languages ). You might want to see what others have to say

Answer 1

I'm only going to review the C++ code here, as all I could suggest for the Python code also applies to the C++, so is included in this review.

Firstly, the interface is quite limiting - the inputs need to be converted to vector of string-view objects, which is inconvenient if I have a linked-list of strings, or an input stream yielding QStrings. I recommend changing to accept a pair of iterators, or in sufficiently modern C++, a std::ranges::range object.

This test is inefficient:

word.find(common, 0) != 0

If we don't find common at position 0, find() will continue searching the rest of the string (the Python code is better here). We need an implementation of starts_with() (which is in C++20's std::string) - or better, we could use std::mismatch() to directly find how much of the strings are common, eliminating the loop where we repeatedly remove a single character.

Here's my attempt at that, also with a simple optimisation to return early when the common string becomes empty:

#include <algorithm>
#include <iterator>
#include <string_view>
#include <vector>
namespace
{
 template<typename String>
 String common_prefix(const String& a, const String& b)
 {
 using std::begin;
 using std::end;
 auto end_iter = std::mismatch(begin(a), end(a), begin(b), end(b));
 if (end_iter.first == end(a)) { return a; }
 if (end_iter.second == end(b)) { return b; }
 return String(begin(a), end_iter.first - begin(a));
 }
}
template<typename Iter, typename IterEnd = Iter>
std::string_view get_common_prefix(Iter first, IterEnd last)
{
 if (first==last) { return ""; }
 std::string_view common = *first;
 for (auto it = first; it != last; ++it) {
 common = common_prefix(common, *it);
 if (common.empty()) { return common; }
 }
 return common;
}
template<typename Container>
std::string_view get_common_prefix(const Container& words)
{
 using std::begin;
 using std::end;
 return get_common_prefix(begin(words), end(words));
}

• Toby Speight: Yes, starts_with() is in C++20. But I didn't dwell on that, because we can do better with our own common_prefix() function.