LeetCode 535. TinyURL 的加密与解密

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 京东
标签
字符串 哈希表 设计 哈希函数

题目描述

✅ 535. TinyURL 的加密与解密

image-20260929101120206

image-20260929101120312

题意分析

实现长网址到短网址的编码与还原，保证 decode(encode(url)) 得到原网址。题目保证解码的短网址由同一个对象编码产生，因此可以把原网址保存在对象中，让短网址只携带一个查询编号。

不同网址需要不同编号，直接使用递增计数器即可。再将编号转成 62 进制，利用数字、大小写字母缩短它的文本表示，最后通过映射表查回完整网址。

解法：哈希映射短链接

核心思路

[!blue]
自增编号生成短码，映射表保存还原关系。 id 记录已经分配到的编号，code2url 保存短码到原网址的映射，url2code 保存原网址到短码的映射。后一个方向让重复编码同一网址时复用已有短码，不再增加编号。

编码时先查 url2code；若是新网址，将 id 加一并转为 62 进制，然后同步写入两张表。在计数器表示范围内，递增编号不会重复，标准 62 进制表示又能唯一确定一个编号，因此新短码不会覆盖另一个网址的记录。

进制转换每次用余数选出当前最低位字符，再整除 62 处理更高位；除法让编号不断缩小，直到变成零。取余得到的是从低位到高位的顺序，最后反转才是标准表示。

返回的短网址由固定前缀和短码组成，而字符表中没有斜杠，所以解码时取最后一个斜杠之后的部分，便能得到原短码。新网址编码时已经登记 code2url[code] = longUrl，重复网址又复用同一个记录，因此所有题目允许的解码调用都能还原正确网址。

解题步骤

  1. 重复网址先查询并复用旧短码。
  2. 新网址增加编号并转换为 62 进制。
  3. 记录双向映射，返回短网址。
  4. decode 提取短码，查回原网址。

代码实现

public class Codec {
    // 在计数器表示范围内，自增编号为新登记的网址生成不同短码。
    private long id = 0;
    private final Map<String, String> code2url = new HashMap<>();
    private final Map<String, String> url2code = new HashMap<>();
    private static final String BASE =
            "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public String encode(String longUrl) {
        // 同一个长链接复用旧短码，判重必须在 id++ 之前。
        String code = url2code.get(longUrl);

        if (code != null) {
            return "http://tinyurl.com/" + code;
        }

        id++;
        code = toBase62(id);
        // 两张表互为逆映射，必须同时写入。
        code2url.put(code, longUrl);
        url2code.put(longUrl, code);

        return "http://tinyurl.com/" + code;
    }

    public String decode(String shortUrl) {
        // 取最后一个 '/' 之后的部分，不依赖前缀的具体长度。
        int idx = shortUrl.lastIndexOf('/');
        String code = idx == -1 ? shortUrl : shortUrl.substring(idx + 1);
        String url = code2url.get(code);

        return url == null ? "" : url;
    }

    private String toBase62(long x) {
        if (x == 0) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        long v = x;

        while (v > 0) {
            int r = (int) (v % 62);

            sb.append(BASE.charAt(r));
            v /= 62;
        }

        // 逐次取余得到低位，最后反转为标准进制表示。
        return sb.reverse().toString();
    }
}

type Codec struct {
    // 在计数器表示范围内，自增编号为新登记的网址生成不同短码。
    id       uint64
    code2url map[string]string
    url2code map[string]string
}

func Constructor() Codec {
    return Codec{code2url: make(map[string]string), url2code: make(map[string]string)}
}

func (this *Codec) encode(longUrl string) string {
    // 同一个长链接复用旧短码，判重必须在 id++ 之前。
    if code, ok := this.url2code[longUrl]; ok {
        return "http://tinyurl.com/" + code
    }
    this.id++
    code := toBase62(this.id)
    // 两张表互为逆映射，必须同时写入。
    this.code2url[code] = longUrl
    this.url2code[longUrl] = code
    return "http://tinyurl.com/" + code
}

func (this *Codec) decode(shortUrl string) string {
    // 取最后一个 '/' 之后的部分，不依赖前缀的具体长度。
    idx := -1
    for i := len(shortUrl) - 1; i >= 0; i-- {
        if shortUrl[i] == '/' {
            idx = i
            break
        }
    }
    code := shortUrl
    if idx != -1 {
        code = shortUrl[idx+1:]
    }
    return this.code2url[code]
}

func toBase62(x uint64) string {
    base := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if x == 0 {
        return "0"
    }
    buf := make([]byte, 0)
    for x > 0 {
        buf = append(buf, base[x%62])
        x /= 62
    }
    // 逐次取余得到低位，最后反转为标准进制表示。
    for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
        buf[i], buf[j] = buf[j], buf[i]
    }
    return string(buf)
}

复杂度分析

  • 时间复杂度：encode 期望 $O(L+K)$，长网址哈希需要读取 $L$ 个字符，进制转换和短网址拼接需要 $O(K)$；decode 期望 $O(K+1)$，用于提取短码和查询映射。$K$ 为短码长度，域名前缀固定。
  • 空间复杂度：累计保存网址内容、短码及映射项，按总字符量和登记数量计。

关键点总结

[!green]

  • 唯一编号与查询表共同保证还原。
  • 重复网址复用是当前实现的行为，由反向映射支持。
  • 两张表在新登记时同时更新。

易错点总结

[!yellow]

  • 直接把有冲突可能的哈希值当唯一短码且不处理冲突：后写入网址可能覆盖旧映射。
  • 只记录网址到短码：无法按短码直接还原。
  • 从第一个斜杠之后提取：会把域名也混入短码。
  • 字符表长度与进制不一致：余数下标可能无效。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/69273991
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！