LeetCode 535: codificar e decodificar TinyURL
Estou postando uma solução para "Encode and Decode TinyURL" do LeetCode. Se você gostaria de revisar, por favor, faça. Obrigado!
Problema
TinyURL é um serviço de encurtamento de URL onde você insere um URL como https://leetcode.com/problems/design-tinyurle ele retorna um URL curto como http://tinyurl.com/4e9iAk.
Projete os métodos encodee decodepara o serviço TinyURL. Não há nenhuma restrição sobre como seu algoritmo de codificação / decodificação deve funcionar. Você só precisa garantir que um URL pode ser codificado para um URL minúsculo e o URL minúsculo pode ser decodificado para o URL original.
Código
// 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));
Respostas
Você está fazendo a pesquisa duas vezes.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Eu sei que é O(1)para consulta. Mas há uma constante real dentro disso. Evite se puder.
Use find(). Então, se estiver lá, você pode simplesmente usá-lo.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Isso é ótimo se você quiser um URL aleatório que seja difícil de adivinhar.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Mas isso é um requisito do quebra-cabeça. Parece (não tenho certeza de quão caro é a geração do número aleatório) que esta é uma forma muito cara de gerar um nome.
Também existe a chance de um confronto. Se você estiver usando valores gerados aleatoriamente, anexe um carimbo de data / hora no final para evitar um conflito.
Pessoalmente, não gosto de precisar especificar um tipo. Mas se você for fazer isso, use o tipo de método em vez de ser tão específico:
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));
Mas acho que simplesmente teria usado emplace().
encoded_url.emplace(long_url, tiny_encoded);
Concordo com tudo na resposta de Martin York. Só uma coisa: você pode evitar ter dois unordered_maps se não criar um URL puramente aleatório, mas sim criar um fazendo o hash do URL original. Dessa forma, você sempre criará a mesma URL minúscula para a mesma URL longa, então você não precisa encoded_urlmais. Claro, você ainda precisaria lidar com duplicatas de alguma forma .
Outros fizeram bons pontos, mas acrescentarei um trocadilho estilístico.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
é um inferno de uma linha. A operadora ternária é divertida, mas falando como alguém que absolutamente abusou dela, se você não conseguir encaixá-la confortavelmente em uma ou duas linhas, você vai se odiar quando voltar a ler isso em 6 meses. Além disso, quando você vê tantos !s correndo por aí, geralmente é hora de quebrar as leis de De Morgan. E isso nos permitiria colocar o caminho desinteressante ainda mais longe de vista. Então, se realmente queremos o ternário ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
ou se eu estava me sentindo um pouco audacioso talvez até
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Eu menti, segundo ponto: eu diria que o C ++ idiomático também deve contar com a conversão de tipo implícita o mínimo possível, ou seja, alterar essa condição para decoded_url.count(...) != 0. É mais detalhado, mas também fica imediatamente mais claro para o leitor o que significa. No entanto, pessoas razoáveis podem discordar.