Awalan umum terpanjang (Leetcode)

Question

Tautkan di sini Saya sedang mempelajari c ++ yang berasal dari latar belakang python, jadi saya akan menyertakan solusi di python dan di c ++ untuk pernyataan masalah di bawah ini, saya menyertakan keduanya untuk kenyamanan, jika Anda tidak tahu c ++, silakan untuk mengulas python dan sebaliknya.

Tulis fungsi untuk menemukan string awalan umum terpanjang di antara larik string. Jika tidak ada awalan umum, kembalikan string kosong "".

Contoh 1:

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

Keluaran: 'fl'

Contoh 2:

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

Keluaran: ''

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'])}")

Statistik Leetcode:

• Durasi: 32 md, lebih cepat dari 76,56% pengiriman online Python3 untuk Awalan Umum Terpanjang.

• Penggunaan Memori: 14 MB, kurang dari 100.00% pengiriman online Python3 untuk Awalan Umum Terpanjang.

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

Statistik Leetcode:

• Durasi: 0 md, lebih cepat dari 100.00% pengiriman online C ++ untuk Awalan Umum Terpanjang.
• Penggunaan Memori: 9,9 MB, kurang dari 7,29% pengiriman online C ++ untuk Awalan Umum Terpanjang.

Answer 1

Saya hanya akan meninjau kode C ++ di sini, karena semua yang saya sarankan untuk kode Python juga berlaku untuk C ++, jadi disertakan dalam ulasan ini.

Pertama, antarmuka cukup membatasi - input perlu diubah menjadi vektor objek tampilan string, yang tidak nyaman jika saya memiliki daftar string yang ditautkan, atau aliran input yang menghasilkan QStrings. Saya sarankan mengubah untuk menerima sepasang iterator, atau di C ++ yang cukup modern, sebuah std::ranges::rangeobjek.

Tes ini tidak efisien:

word.find(common, 0) != 0

Jika kami tidak menemukan commondi posisi 0, find()akan terus mencari sisa string (kode Python lebih baik di sini). Kita membutuhkan implementasi starts_with()(yang ada di C ++ 20 std::string) - atau lebih baik, kita bisa menggunakan std::mismatch()untuk menemukan secara langsung berapa banyak string yang umum, menghilangkan loop di mana kita berulang kali menghapus satu karakter.

Inilah upaya saya untuk itu, juga dengan pengoptimalan sederhana untuk kembali lebih awal ketika string umum menjadi kosong:

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