Tiền tố chung dài nhất (Leetcode)

Question

Liên kết ở đây Tôi hiện đang học c ++ đến từ nền tảng python, vì vậy tôi sẽ bao gồm một giải pháp trong python và trong c ++ cho câu lệnh vấn đề bên dưới, tôi bao gồm cả hai để thuận tiện, nếu bạn không biết c ++, vui lòng để xem lại python và ngược lại.

Viết một hàm để tìm chuỗi tiền tố chung dài nhất trong số một mảng các chuỗi. Nếu không có tiền tố chung, hãy trả về một chuỗi rỗng "".

Ví dụ 1:

Đầu vào: words = ['flower', 'flow', 'flight']

Đầu ra: 'fl'

Ví dụ 2:

Đầu vào: strs = ['dog', 'racecar', 'car']

Đầu ra: ''

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

Thống kê Leetcode:

• Thời gian chạy: 32 mili giây, nhanh hơn 76,56% số lần gửi trực tuyến Python3 cho Tiền tố chung dài nhất.

• Sử dụng bộ nhớ: 14 MB, ít hơn 100,00% số lần gửi trực tuyến Python3 cho Tiền tố chung dài nhất.

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

Thống kê Leetcode:

• Thời gian chạy: 0 ms, nhanh hơn 100,00% số lần gửi trực tuyến C ++ cho Tiền tố chung dài nhất.
• Sử dụng bộ nhớ: 9,9 MB, ít hơn 7,29% số lần gửi trực tuyến C ++ cho Tiền tố chung dài nhất.

Answer 1

Tôi sẽ chỉ xem xét mã C ++ ở đây, vì tất cả những gì tôi có thể đề xuất cho mã Python cũng áp dụng cho C ++, do đó, được bao gồm trong bài đánh giá này.

Thứ nhất, giao diện khá hạn chế - các đầu vào cần được chuyển đổi thành vectơ của các đối tượng dạng xem chuỗi, điều này thật bất tiện nếu tôi có danh sách các chuỗi được liên kết hoặc luồng đầu vào mang lại QStrings. Tôi khuyên bạn nên thay đổi để chấp nhận một cặp trình vòng lặp hoặc trong C ++ đủ hiện đại, một std::ranges::rangeđối tượng.

Thử nghiệm này không hiệu quả:

word.find(common, 0) != 0

Nếu chúng tôi không tìm thấy commonở vị trí 0, find()sẽ tiếp tục tìm kiếm phần còn lại của chuỗi (mã Python ở đây tốt hơn). Chúng ta cần triển khai starts_with()(trong C ++ 20's std::string) - hoặc tốt hơn, chúng ta có thể sử dụng std::mismatch()để tìm trực tiếp bao nhiêu chuỗi là chung, loại bỏ vòng lặp mà chúng ta liên tục xóa một ký tự.

Đây là nỗ lực của tôi về điều đó, cũng với một tối ưu hóa đơn giản để trả về sớm khi chuỗi chung trở nên trống:

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