LeetCode 535 : TinyURL 인코딩 및 디코딩

Question

LeetCode의 "Encode and Decode TinyURL"에 대한 솔루션을 게시하고 있습니다. 리뷰를 원하시면 해주세요. 감사합니다!

문제

티니 URL은 같은 URL을 입력의 URL 단축 서비스입니다 https://leetcode.com/problems/design-tinyurl과 같은 짧은 URL을 반환합니다 http://tinyurl.com/4e9iAk.

TinyURL 서비스에 대한 encode및 decode메서드를 디자인합니다 . 인코딩 / 디코딩 알고리즘의 작동 방식에는 제한이 없습니다. URL을 작은 URL로 인코딩하고 작은 URL을 원래 URL로 디코딩 할 수 있는지 확인하기 만하면됩니다.

암호

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <utility>
#include <random>

static const struct Solution {
    public:
        const std::string encode(
            const std::string long_url
        ) {
            std::string tiny_encoded;

            if (!encoded_url.count(long_url)) {
                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

                encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));
                decoded_url.insert(std::pair<std::string, std::string>(tiny_encoded, long_url));

            } else {
                tiny_encoded = encoded_url[long_url];
            }

            return kDomain + tiny_encoded;
        }

        const std::string decode(
            const std::string short_url
        ) {

            return std::size(short_url) != kDomainTinySize ||
                   !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
                   decoded_url[short_url.substr(kDomainSize, kTinySize)];
        }

    private:
        static constexpr char kDomain[] = "http://tinyurl.com/";
        static constexpr unsigned int kTinySize = 6;
        static constexpr unsigned int kDomainSize = std::size(kDomain) - 1;
        static constexpr auto kDomainTinySize = kDomainSize + kTinySize;
        static constexpr char char_pool[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        std::unordered_map<std::string, std::string> encoded_url;
        std::unordered_map<std::string, std::string> decoded_url;
        std::random_device rand_generator;
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

Answer 1

조회를 두 번 수행하고 있습니다.

            if (!encoded_url.count(long_url)) {

                .. stuff

            } else {
                tiny_encoded = encoded_url[long_url];
            }

나는 그것이 O(1)조회 용 이라는 것을 알고 있습니다. 하지만 그 안에 진짜 상수가 있습니다. 가능하면 피하십시오.

사용 find(). 그런 다음 거기에 있으면 간단히 사용할 수 있습니다.

            auto find = encoded_url.find(long_url);
            if (find == encoded_url.end()) {

                .. stuff

            } else {
                tiny_encoded = find->second;
            }

---

추측하기 어려운 임의의 URL을 원하는 경우 유용합니다.

                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

그러나 그것이 퍼즐의 요구 사항입니다. (난수를 생성하는 데 얼마나 많은 비용이 드는지 확실하지 않음) 이름을 생성하는 데 매우 비용이 많이 드는 방법 인 것 같습니다.

충돌의 기회도 있습니다. 임의로 생성 된 값을 사용하는 경우 충돌을 피하기 위해 끝에 타임 스탬프를 추가합니다.

---

개인적으로 나는 유형을 지정하는 것을 좋아하지 않습니다. 그러나 만약 당신이 그것을하려고한다면 이렇게 구체적이지 않고 방법의 유형을 사용하십시오 :

    encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));


    // Top of the class.
    using Map      = std::unordered_map<std::string, std::string>;
    using MapValue = Map::value_type;

    // In the code.
    encoded_url.insert(MapValue(long_url, tiny_encoded));

그러나 나는 단순히 emplace().

    encoded_url.emplace(long_url, tiny_encoded);

---

Answer 2

나는 Martin York의 대답에있는 모든 것에 동의합니다. 한 가지만 : unordered_map순전히 임의의 URL을 만들지 않고 원래 URL을 해싱하여 하나를 만들면 두 개의 s를 피할 수 있습니다 . 이렇게하면 동일한 긴 URL에 대해 항상 동일한 작은 URL을 만들 수 있으므로 encoded_url더 이상 필요 하지 않습니다. 물론 어떤 방식 으로든 중복을 처리해야합니다 .

Answer 3

다른 사람들은 좋은 지적을했지만, 나는 문체에 대한 말을 덧붙일 것입니다.

return std::size(short_url) != kDomainTinySize ||
       !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
       decoded_url[short_url.substr(kDomainSize, kTinySize)];

도대체 한 줄짜리입니다. 삼항 연산자는 재미 있지만 절대적으로 그것을 남용한 사람으로 말하면 한두 줄에 편안하게 맞출 수 없다면 6 개월 후에 다시 읽으면 자신을 미워하게 될 것입니다. 또한 많은 사람들이 !돌아 다니는 것을 볼 때 일반적으로 De Morgan의 법칙을 깨뜨릴 때입니다. 그리고 그것은 우리가 흥미롭지 않은 길을 눈에 띄지 않게 만들 것입니다. 그래서 우리가 정말로 삼항을 원한다면 ...

return std::size(short_url) == kDomainTinySize &&
       decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
       decoded_url[short_url.substr(kDomainSize, kTinySize)] :
       "";

또는 내가 조금 대담한 느낌이 든다면

return std::size(short_url) == kDomainTinySize 
       && decoded_url.count(short_url.substr(kDomainSize, kTinySize))
       ? decoded_url[short_url.substr(kDomainSize, kTinySize)]
       : "";

두 번째 요점은 다음과 같습니다. 관용적 C ++는 암시 적 형식 변환에 가능한 한 적게 의존해야합니다 decoded_url.count(...) != 0. 즉, 해당 조건을 . 더 장황하지만 의미가 무엇인지 독자에게 즉시 더 명확합니다. 합리적인 사람들은 동의하지 않을 수 있습니다.