1
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ I posted a question on meta taking this into consideration( 2 languages ). You might want to see what others have to say \$\endgroup\$
    – user228914
    Nov 5, 2020 at 3:44

1 Answer 1

4
\$\begingroup\$

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));
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ Nov 5, 2020 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.