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.

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));
}