En uzun ortak önek (Leetcode)

Question

Buraya bağlantı verin Şu anda bir python arka planından gelen c ++ öğreniyorum, bu nedenle aşağıdaki problem ifadesi için python ve c ++ 'da bir çözüm ekleyeceğim, her ikisini de kolaylık için ekliyorum, c ++ bilmiyorsanız, çekinmeyin python ve tersini gözden geçirmek için.

Bir dizge dizisi arasında en uzun ortak önek dizesini bulmak için bir işlev yazın. Ortak bir önek yoksa, boş bir "" dizesi döndürün.

Örnek 1:

Giriş: words = ['flower', 'flow', 'flight']

Çıktı: 'fl'

Örnek 2:

Giriş: strs = ['dog', 'racecar', 'car']

Çıktı: ''

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 istatistikleri:

• Çalışma Süresi: En Uzun Ortak Önek için Python3 çevrimiçi gönderimlerinin% 76,56'sından daha hızlı 32 ms.

• Bellek Kullanımı: 14 MB, En Uzun Yaygın Önek için Python3 çevrimiçi gönderimlerinin% 100.00'ünden az.

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 istatistikleri:

• Çalışma Zamanı: 0 ms, En Uzun Ortak Önek için C ++ çevrimiçi gönderimlerinin% 100.00'ünden daha hızlı.
• Bellek Kullanımı: 9,9 MB, En Uzun Ortak Önek için C ++ çevrimiçi gönderimlerinin% 7,29'undan azı.

Answer 1

Python kodu için önerebileceğim her şey C ++ için de geçerli olduğundan, bu incelemeye dahil edildiğinden, burada yalnızca C ++ kodunu gözden geçireceğim.

İlk olarak, arayüz oldukça sınırlayıcıdır - girişlerin, dizge görünümü nesnelerinin vektörüne dönüştürülmesi gerekir; bu, bağlantılı bir dizgi listesine veya QStrings veren bir girdi akışına sahipsem rahatsızlık verir . Bir çift yineleyiciyi veya yeterince modern C ++ 'da bir std::ranges::rangenesneyi kabul etmek için değiştirmenizi öneririm .

Bu test verimsiz:

word.find(common, 0) != 0

common0 konumunda bulamazsak find(), dizenin geri kalanını aramaya devam edeceğiz (Python kodu burada daha iyidir). starts_with()(C ++ 20'lerde olan std::string) bir uygulamasına ihtiyacımız var - veya daha iyisi, std::mismatch()dizelerin ne kadarının ortak olduğunu doğrudan bulmak için kullanabiliriz , böylece tek bir karakteri defalarca kaldırdığımız döngüyü ortadan kaldırabiliriz.

İşte benim bunu denemem, ayrıca ortak dizge boşaldığında erken dönmek için basit bir optimizasyonla:

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