535. TinyURL 的加密与解密

题目描述

实现一个网址缩短服务的类 Codec（部分语言中叫 Solution），它能把一个很长的网址换成一个简短的链接（比如以 http://tinyurl.com/ 开头的形式），也能把短链接还原回来。

需要实现的方法：构造函数创建一个空的服务对象；encode(longUrl) 接收一个长网址，返回为它生成的短网址；decode(shortUrl) 接收一个短网址，返回它对应的原始长网址。

具体的编码规则由你决定，唯一的要求是对任意合法网址 url，decode(encode(url)) 必须得到原来的 url。传给 decode 的短网址保证由同一个对象的 encode 生成。

示例 1

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

解释：先调用 encode 得到短网址，再对它调用 decode，结果就是原网址。

数据范围

1 <= url.length <= 10^4
保证 url 是合法的网址。

解题思路：自增 ID + 62 进制

用自增计数器给每个长链接发一个编号 id，把 id 转成 62 进制字符串（0-9a-zA-Z）作为短码，并在哈希表 db 中记下短码 → 长链接。encode 返回前缀 + 短码；decode 截掉前缀得到短码，再查 db。

为什么正确

id 只增不减，所以发出的短码两两不同；db 中每个短码恰好对应一个长链接，decode 查到的一定是 encode 时存入的那个。

复杂度分析

encode 需转换 O(log62 id) 位，decode 截取短码 O(L)、查表 O(1)；db 存所有链接，空间 O(总长度)。

易错点

短码应基于计数器或检查冲突，直接取哈希截断可能两个链接撞到同一个短码；JS/TS 的 db 若写在函数外，多个测试用例会共享，id 必须一直递增而不是每次从头开始，否则旧短码会被覆盖。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

class Codec:
    def __init__(self):
        self.db = {}
        self.id = 0

    def encode(self, longUrl: str) -> str:
        self.id += 1
        n, code = self.id, ''
        while n > 0:
            code = CHARS[n % 62] + code
            n //= 62
        self.db[code] = longUrl
        return 'http://tinyurl.com/' + code

    def decode(self, shortUrl: str) -> str:
        code = shortUrl[len('http://tinyurl.com/'):]
        return self.db[code]

class Codec {
    static final String CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private Map<String, String> db = new HashMap<>();
    private long id = 0;

    public String encode(String longUrl) {
        id++;
        long n = id; String code = "";
        while (n > 0) {
            code = CHARS.charAt((int) (n % 62)) + code;
            n /= 62;
        }
        db.put(code, longUrl);
        return "http://tinyurl.com/" + code;
    }

    public String decode(String shortUrl) {
        String code = shortUrl.substring("http://tinyurl.com/".length());
        return db.get(code);
    }
}

const string CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

class Solution {
    unordered_map<string, string> db;
    long long id = 0;
public:
    string encode(string longUrl) {
        id++;
        long long n = id; string code = "";
        while (n > 0) {
            code = CHARS[n % 62] + code;
            n /= 62;
        }
        db[code] = longUrl;
        return "http://tinyurl.com/" + code;
    }

    string decode(string shortUrl) {
        string code = shortUrl.substr(string("http://tinyurl.com/").size());
        return db[code];
    }
};

const CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

type Codec struct {
	db map[string]string
	id int
}

func Constructor() Codec {
	return Codec{db: map[string]string{}}
}

func (this *Codec) encode(longUrl string) string {
	this.id++
	n, code := this.id, ""
	for n > 0 {
		code = string(CHARS[n%62]) + code
		n /= 62
	}
	this.db[code] = longUrl
	return "http://tinyurl.com/" + code
}

func (this *Codec) decode(shortUrl string) string {
	code := shortUrl[len("http://tinyurl.com/"):]
	return this.db[code]
}

const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const db = new Map();
let id = 0;

var encode = function(longUrl) {
    id++;
    let n = id, code = '';
    while (n > 0) {
        code = CHARS[n % 62] + code;
        n = Math.floor(n / 62);
    }
    db.set(code, longUrl);
    return 'http://tinyurl.com/' + code;
};

var decode = function(shortUrl) {
    const code = shortUrl.slice('http://tinyurl.com/'.length);
    return db.get(code);
};

const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const db = new Map<string, string>();
let id = 0;

function encode(longUrl: string): string {
    id++;
    let n = id, code = '';
    while (n > 0) {
        code = CHARS[n % 62] + code;
        n = Math.floor(n / 62);
    }
    db.set(code, longUrl);
    return 'http://tinyurl.com/' + code;
}

function decode(shortUrl: string): string {
    const code = shortUrl.slice('http://tinyurl.com/'.length);
    return db.get(code)!;
}

载入编辑器，自己跑一遍 →

其他解法

自增 ID 保证不冲突且短码最短，但会暴露生成顺序；随机短码长度固定、不可预测，需要冲突检测。L 为网址长度。

解法 2：随机生成短码时间 O(L)，空间 O(L)

每次编码时从 62 个字符中随机取 6 个拼成短码。如果短码已经在表中，就重新生成。确认唯一后把短码映射到长网址。解码时直接按短码查表。

短码不可预测，别人无法按顺序猜出其他链接。代价是要处理冲突，表越满重试越多；6 位 62 进制约有 5.7×10¹⁰ 种取值，实际几乎不冲突。

import random

CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

class Codec:
    def __init__(self):
        self.db = {}

    def encode(self, longUrl: str) -> str:
        while True:
            code = ''.join(random.choice(CHARS) for _ in range(6))
            if code not in self.db:
                break
        self.db[code] = longUrl
        return 'http://tinyurl.com/' + code

    def decode(self, shortUrl: str) -> str:
        code = shortUrl[len('http://tinyurl.com/'):]
        return self.db[code]

class Codec {
    static final String CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private Map<String, String> db = new HashMap<>();
    private Random rng = new Random();

    public String encode(String longUrl) {
        String code;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) sb.append(CHARS.charAt(rng.nextInt(62)));
            code = sb.toString();
        } while (db.containsKey(code));
        db.put(code, longUrl);
        return "http://tinyurl.com/" + code;
    }

    public String decode(String shortUrl) {
        String code = shortUrl.substring("http://tinyurl.com/".length());
        return db.get(code);
    }
}

const string CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

class Solution {
    unordered_map<string, string> db;
    mt19937 rng{random_device{}()};
public:
    string encode(string longUrl) {
        string code;
        do {
            code.clear();
            for (int i = 0; i < 6; i++) code += CHARS[rng() % 62];
        } while (db.count(code));
        db[code] = longUrl;
        return "http://tinyurl.com/" + code;
    }

    string decode(string shortUrl) {
        string code = shortUrl.substr(string("http://tinyurl.com/").size());
        return db[code];
    }
};

const CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

type Codec struct {
	db map[string]string
}

func Constructor() Codec {
	return Codec{db: map[string]string{}}
}

func (this *Codec) encode(longUrl string) string {
	var code string
	for {
		b := make([]byte, 6)
		for i := range b {
			b[i] = CHARS[rand.Intn(62)]
		}
		code = string(b)
		if _, ok := this.db[code]; !ok {
			break
		}
	}
	this.db[code] = longUrl
	return "http://tinyurl.com/" + code
}

func (this *Codec) decode(shortUrl string) string {
	code := shortUrl[len("http://tinyurl.com/"):]
	return this.db[code]
}

const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const db = new Map();

var encode = function(longUrl) {
    let code;
    do {
        code = '';
        for (let i = 0; i < 6; i++) code += CHARS[Math.floor(Math.random() * 62)];
    } while (db.has(code));
    db.set(code, longUrl);
    return 'http://tinyurl.com/' + code;
};

var decode = function(shortUrl) {
    const code = shortUrl.slice('http://tinyurl.com/'.length);
    return db.get(code);
};

const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const db = new Map<string, string>();

function encode(longUrl: string): string {
    let code: string;
    do {
        code = '';
        for (let i = 0; i < 6; i++) code += CHARS[Math.floor(Math.random() * 62)];
    } while (db.has(code));
    db.set(code, longUrl);
    return 'http://tinyurl.com/' + code;
}

function decode(shortUrl: string): string {
    const code = shortUrl.slice('http://tinyurl.com/'.length);
    return db.get(code)!;
}

设计专题的其他题目

查看设计全部题目 →