LeetCode 535: Codificar y decodificar TinyURL
Estoy publicando una solución para "Encode and Decode TinyURL" de LeetCode. Si desea revisarlo, hágalo. ¡Gracias!
Problema
TinyURL es un servicio de acortamiento de URL en el que ingresa una URL como https://leetcode.com/problems/design-tinyurly devuelve una URL corta como http://tinyurl.com/4e9iAk.
Diseñe los métodos encodey decodepara el servicio TinyURL. No hay restricciones sobre cómo debería funcionar su algoritmo de codificación / decodificación. Solo necesita asegurarse de que una URL se pueda codificar en una URL pequeña y que la URL pequeña se pueda decodificar en la 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));
Respuestas
Estás haciendo la búsqueda dos veces.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Sé que es O(1)para la búsqueda. Pero hay una constante real dentro de eso. Evitalo si puedes.
Utilice find(). Entonces, si está allí, simplemente puede usarlo.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Esto es genial si desea una URL aleatoria que sea difícil de adivinar.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Pero, ¿es ese un requisito del rompecabezas? Parece (no estoy seguro de cuán caro es generar el número aleatorio) que esta es una forma muy costosa de generar un nombre.
También existe la posibilidad de un choque. Si está utilizando valores generados aleatoriamente, agregue una marca de tiempo al final para evitar un conflicto.
Personalmente, no me gusta tener que especificar un tipo. Pero si va a hacerlo, use el tipo de método en lugar de ser tan 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));
Pero creo que simplemente lo hubiera usado emplace().
encoded_url.emplace(long_url, tiny_encoded);
Estoy de acuerdo con todo en la respuesta de Martin York. Solo una cosa: puede evitar tener dos unordered_maps si no crea una URL puramente aleatoria, sino que crea una mediante el hash de la URL original. De esta manera, siempre creará la misma URL pequeña para la misma URL larga, por lo que no necesitará encoded_urlmás. Por supuesto, aún necesitaría manejar duplicados de alguna manera .
Otros han hecho buenos puntos, pero agregaré una objeción estilística.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
es un diablo de una sola línea. El operador ternario es divertido, pero hablando como alguien que ha abusado absolutamente de él, si no puede colocarlo cómodamente en una línea o dos, entonces se odiará a sí mismo cuando vuelva a leer eso en 6 meses. Además, cuando ves que hay muchas personas !corriendo, suele ser el momento de romper las leyes de De Morgan. Y nos permitiría esconder aún más el camino poco interesante. Entonces, si realmente queremos el ternario ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
o si me sentía un poco audaz tal vez incluso
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Mentí, segundo punto: diría que el C ++ idiomático también debería depender de la conversión de tipo implícita lo menos posible, es decir, cambiar esa condición a decoded_url.count(...) != 0. Es más detallado, pero también es inmediatamente más claro para el lector lo que significa. Sin embargo, las personas razonables podrían no estar de acuerdo.