Medium

题目描述

注意：这是系统设计问题：设计 TinyURL 的配套问题。

TinyURL 是一种 URL 缩短服务，您可以在其中输入 URL（例如 https://leetcode.com/problems/design-tinyurl），它会返回一个短 URL（例如 http://tinyurl.com/4e9iAk）。设计一个类来编码 URL 和解码短 URL。

对于您的编码/解码算法如何工作没有限制。您只需要确保一个 URL 可以被编码为短 URL，并且短 URL 可以被解码为原始 URL。

实现 Solution 类：

  • Solution() 初始化系统对象。
  • String encode(String longUrl) 为给定的 longUrl 返回一个短 URL。
  • String decode(String shortUrl) 为给定的 shortUrl 返回原始长 URL。保证给定的 shortUrl 是由同一个对象编码的。

示例 1：

输入：url = "https://leetcode.com/problems/design-tinyurl"
输出："https://leetcode.com/problems/design-tinyurl"

解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回编码的短 url
string ans = obj.decode(tiny); // 返回解码后的原始 url

约束条件：

  • 1 <= url.length <= 10^4
  • url 保证是一个有效的 URL。

解题思路

这个问题有多种解法思路：

方法一：基于计数器的简单编码 使用一个递增的计数器为每个长 URL 分配一个唯一的数字 ID，然后将这个 ID 作为短 URL 的后缀。这种方法简单高效，编码后的 URL 长度较短。

方法二：基于哈希的编码 使用哈希函数（如 MD5 或 SHA）对长 URL 进行哈希，取哈希值的前几位作为短 URL 的标识符。需要处理哈希冲突问题。

方法三：随机字符串生成 为每个长 URL 生成一个随机的字符串作为短 URL 标识符，需要确保不会产生重复。

本题解采用方法一（推荐），因为它实现简单、性能好，且在实际场景中很实用。我们维护两个哈希表：一个用于从长 URL 到短 URL 的映射，另一个用于从短 URL 到长 URL 的反向映射。使用递增计数器确保每个短 URL 都是唯一的。

这种方法的优点是：

  1. 编码速度快，时间复杂度 O(1)
  2. 生成的短 URL 长度短且规律
  3. 不存在冲突问题
  4. 易于实现和维护

代码实现

class Solution {
private:
    unordered_map<string, string> longToShort;
    unordered_map<string, string> shortToLong;
    int counter;
    string baseUrl = "http://tinyurl.com/";
    
public:
    Solution() : counter(0) {}
    
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if (longToShort.find(longUrl) != longToShort.end()) {
            return longToShort[longUrl];
        }
        
        string shortUrl = baseUrl + to_string(counter++);
        longToShort[longUrl] = shortUrl;
        shortToLong[shortUrl] = longUrl;
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return shortToLong[shortUrl];
    }
};

class Codec:
    def __init__(self):
        self.long_to_short = {}
        self.short_to_long = {}
        self.counter = 0
        self.base_url = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        if longUrl in self.long_to_short:
            return self.long_to_short[longUrl]
        
        short_url = self.base_url + str(self.counter)
        self.counter += 1
        
        self.long_to_short[longUrl] = short_url
        self.short_to_long[short_url] = longUrl
        
        return short_url

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.short_to_long[shortUrl]

public class Codec {
    private Dictionary<string, string> longToShort;
    private Dictionary<string, string> shortToLong;
    private int counter;
    private string baseUrl = "http://tinyurl.com/";
    
    public Codec() {
        longToShort = new Dictionary<string, string>();
        shortToLong = new Dictionary<string, string>();
        counter = 0;
    }

    // Encodes a URL to a shortened URL
    public string encode(string longUrl) {
        if (longToShort.ContainsKey(longUrl)) {
            return longToShort[longUrl];
        }
        
        string shortUrl = baseUrl + counter.ToString();
        counter++;
        
        longToShort[longUrl] = shortUrl;
        shortToLong[shortUrl] = longUrl;
        
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    public string decode(string shortUrl) {
        return shortToLong[shortUrl];
    }
}

var counter = 0;
var longToShort = new Map();
var shortToLong = new Map();
var baseUrl = "http://tinyurl.com/";

/**
 * Encodes a URL to a shortened URL.
 *
 * @param {string} longUrl
 * @return {string}
 */
var encode = function(longUrl) {
    if (longToShort.has(longUrl)) {
        return longToShort.get(longUrl);
    }
    
    var shortUrl = baseUrl + counter.toString();
    counter++;
    
    longToShort.set(longUrl, shortUrl);
    shortToLong.set(shortUrl, longUrl);
    
    return shortUrl;
};

/**
 * Decodes a shortened URL to its original URL.
 *
 * @param {string} shortUrl
 * @return {string}
 */
var decode = function(shortUrl) {
    return shortToLong.get(shortUrl);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
encodeO(1)O(n)
decodeO(1)O(n)

其中 n 是已编码的 URL 数量。空间复杂度主要用于存储两个哈希表的映射关系。