Самый длинный общий префикс (Leetcode)

Question

Ссылка здесь. В настоящее время я изучаю C ++ на базе Python, поэтому я включу решение на Python и на C ++ для приведенной ниже постановки проблемы, я включаю оба для удобства, если вы не знаете C ++, не стесняйтесь для обзора Python и наоборот.

Напишите функцию для поиска самой длинной строки общего префикса среди массива строк. Если общего префикса нет, вернуть пустую строку «».

Пример 1:

Вход: words = ['flower', 'flow', 'flight']

Вывод: 'fl'

Пример 2:

Вход: strs = ['dog', 'racecar', 'car']

Вывод: ''

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:

• Время выполнения: 32 мс, быстрее, чем 76,56% онлайн-представлений Python3 для самого длинного общего префикса.

• Использование памяти: 14 МБ, менее 100,00% онлайн-представлений Python3 для самого длинного общего префикса.

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:

• Время выполнения: 0 мс, быстрее, чем 100,00% онлайн-представлений C ++ для самого длинного общего префикса.
• Использование памяти: 9,9 МБ, менее 7,29% онлайн-представлений C ++ для самого длинного общего префикса.

Answer 1

Я собираюсь рассмотреть здесь только код C ++, так как все, что я мог предложить для кода Python, также применимо к C ++, поэтому оно включено в этот обзор.

Во-первых, интерфейс довольно ограничен - входные данные необходимо преобразовать в вектор объектов строкового представления, что неудобно, если у меня есть связанный список строк или входной поток, дающий QStrings. Я рекомендую изменить, чтобы принять пару итераторов или, в достаточно современном C ++, std::ranges::rangeобъект.

Этот тест неэффективен:

word.find(common, 0) != 0

Если мы не найдем commonв позиции 0, find()мы продолжим поиск в оставшейся части строки (код Python здесь лучше). Нам нужна реализация starts_with()(которая есть в C ++ 20 std::string) - или, что лучше, мы могли бы использовать, std::mismatch()чтобы напрямую определить, сколько строк является общим, исключив цикл, в котором мы многократно удаляем один символ.

Вот моя попытка сделать это, также с простой оптимизацией, чтобы вернуться раньше, когда общая строка станет пустой:

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