LeetCode 535: codifica e decodifica TinyURL
Sto postando una soluzione per "Encode and Decode TinyURL" di LeetCode. Se desideri rivedere, fallo. Grazie!
Problema
TinyURL è un servizio di accorciamento di URL in cui inserisci un URL come https://leetcode.com/problems/design-tinyurle restituisce un URL breve come http://tinyurl.com/4e9iAk.
Progettare i metodi encodee decodeper il servizio TinyURL. Non ci sono restrizioni su come dovrebbe funzionare il tuo algoritmo di codifica / decodifica. Devi solo assicurarti che un URL possa essere codificato in un piccolo URL e che il piccolo URL possa essere decodificato nell'URL originale.
Codice
// 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));
Risposte
Stai facendo la ricerca due volte.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
So che è O(1)per la ricerca. Ma c'è una vera costante al suo interno. Evitalo se puoi.
Usa find(). Quindi se è lì puoi semplicemente usarlo.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Questo è ottimo se desideri URL casuali difficili da indovinare.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Ma è questo un requisito del puzzle. Sembra (non sono sicuro di quanto sia costoso generare il numero casuale) come questo sia un modo molto costoso per generare un nome.
C'è anche la possibilità di uno scontro. Se stai utilizzando valori generati casualmente, aggiungi un timestamp all'estremità per evitare uno scontro.
Personalmente non mi piace dover specificare un tipo. Ma se hai intenzione di farlo usa il tipo di metodo piuttosto che essere così specifico:
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));
Ma penso che avrei semplicemente usato emplace().
encoded_url.emplace(long_url, tiny_encoded);
Sono d'accordo con tutto nella risposta di Martin York. Solo una cosa: puoi evitare di averne due unordered_mapse non crei un URL puramente casuale, ma invece ne crei uno eseguendo l'hashing dell'URL originale. In questo modo, creerai sempre lo stesso minuscolo URL per lo stesso URL lungo, quindi non ne avrai encoded_urlpiù bisogno . Ovviamente, dovresti comunque gestire i duplicati in qualche modo .
Altri hanno espresso buoni punti, ma aggiungerò un cavillo stilistico.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
è un diavolo di una battuta. L'operatore ternario è divertente ma parla come qualcuno che ne ha assolutamente abusato, se non riesci a metterlo comodamente su una riga o due allora ti odierai quando tornerai a leggerlo tra 6 mesi. Inoltre, quando vedi che molti !stanno correndo in giro, di solito è il momento di infrangere le leggi di De Morgan. E ci permetterebbe di nascondere ulteriormente il percorso poco interessante. Quindi, se vogliamo davvero il ternario ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
o se mi sentivo un po 'audace forse anche
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Ho mentito, secondo punto: direi che il C ++ idiomatico dovrebbe anche fare affidamento sulla conversione del tipo implicita il meno possibile, vale a dire, cambiare quella condizione in decoded_url.count(...) != 0. È più prolisso, ma è anche immediatamente più chiaro per il lettore cosa si intende. Le persone ragionevoli potrebbero tuttavia non essere d'accordo.