LeetCode 535在 LeetCode-Go 中用 Go 实现 TinyURL 编解码Encode and Decode TinyURL【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoTinyURL 是一种经典的 URL 缩短服务输入一个冗长的原始 URL输出一个形如http://tinyurl.com/4e9iAk的短链接并且这个短链接可以重新解码还原成原始 URL。本文以 LeetCode 535 题「Encode and Decode TinyURL」为骨架结合开源仓库 LeetCode-Go 中的完整 Go 实现、源码细节与测试用例讲解下标索引法的编码/解码设计思路、边界分析与本地验证方式帮助读者掌握这类「无限制算法设计 双向映射保证」题型的标准解法。题目背景TinyURL 是什么本题原题LeetCode 535在仓库对应文档 leetcode/0535.Encode-and-Decode-TinyURL/README.md 中给出了完整描述并特别注明本题是系统设计题「Design TinyURL」的伴生问题companion problem。也就是说OJ 里的这道题要求的是功能正确性——只要 encode/decode 互逆即可而真正的系统设计题则要额外考虑高并发、存储、短码碰撞、跳转性能等架构问题。用题目中的例子来说输入原始 URLhttps://leetcode.com/problems/design-tinyurl返回短 URLhttp://tinyurl.com/4e9iAk服务需要提供两个方法encode(longUrl)把长 URL 编码成短 URLdecode(shortUrl)把短 URL 解码还原成原始 URL。题目要求解析算法自由互逆是底线题目对算法设计没有任何硬性限制不要求短码长度固定、不要求不可碰撞、不要求无状态。唯一必须满足的约束是一个 URL 可以被编码成一个 TinyURL并且这个 TinyURL 可以被解码恢复成原本的 URL。用数学语言描述就是decode(encode(url)) url必须对任意合法输入成立。这正是本题「简单题」定位的根源——自由度极高最简单的做法就能通过全部用例。解题思路用数组下标建立双向映射仓库 README 给出的核心思路非常直白编码把原始 URL 追加到一个字符串数组切片末尾数组的下标从 0 开始递增的自然数就是该 URL 的「短码」返回将下标拼接到固定前缀http://tinyurl.com/后面构成短 URL解码从短 URL 中解析出末尾的下标数字用它去数组中取回原始 URL。这一方案的本质是用数组下标充当全局唯一的自增 ID每次 encode 必然产生一个与之前所有下标都不重复的新下标因此天然没有碰撞问题decode 也必定能命中唯一的原始 URL。整个过程的时间复杂度均为 O(1)。源码实现逐行解析仓库中的完整实现位于 535. Encode and Decode TinyURL.go与 README 中的代码完全一致。下面逐段分析。1. 数据结构Codec 与 URL 存储type Codec struct { urls []string } func Constructor() Codec { return Codec{[]string{}} }Codec结构体内部只有一个urls []string切片作为短码 → 原始 URL 的映射存储下标即短码值即原始 URLConstructor()负责初始化一个空的Codec实例对应题目注释中要求的调用方式obj : Constructor()。注意这里有个隐性约定urls的下标恰好是自增的。第一次 encode 存入下标 0第二次存入下标 1依此类推天然构成「第 N 次编码 → 短码 N」的一一映射。2. 编码encode// Encodes a URL to a shortened URL. func (this *Codec) encode(longUrl string) string { this.urls append(this.urls, longUrl) return http://tinyurl.com/ fmt.Sprintf(%v, len(this.urls)-1) }实现要点对应源码 535. Encode and Decode TinyURL.goappend(this.urls, longUrl)把长 URL 存入切片末尾len(this.urls)-1得到刚存入元素的下标也就是本次分配的短码用fmt.Sprintf(%v, ...)把整数下标转成字符串拼接固定前缀http://tinyurl.com/后返回。举例第一次调用encode(https://leetcode.com/problems/design-tinyurl)urls变为[https://leetcode.com/problems/design-tinyurl]返回http://tinyurl.com/0。第二次调用则返回http://tinyurl.com/1以此类推。3. 解码decode// Decodes a shortened URL to its original URL. func (this *Codec) decode(shortUrl string) string { tmp : strings.Split(shortUrl, /) i, _ : strconv.Atoi(tmp[len(tmp)-1]) return this.urls[i] }实现要点对应源码 535. Encode and Decode TinyURL.gostrings.Split(shortUrl, /)按/切分短 URL例如http://tinyurl.com/0切分为[http:, , tinyurl.com, 0]取最后一段tmp[len(tmp)-1]即短码字符串strconv.Atoi(...)把短码字符串转回整数下标this.urls[i]按下标取回原始 URL。4. 使用方式源码文件末尾保留了题目给出的调用契约注释/** * Your Codec object will be instantiated and called as such: * obj : Constructor(); * url : obj.encode(longUrl); * ans : obj.decode(url); */即先Constructor()构造实例再encode生成短 URL最后decode还原。三段式调用在下面的测试用例中会完整走一遍。复杂度与正确性分析维度分析encode 时间复杂度O(1)仅一次append与一次字符串拼接decode 时间复杂度O(L)L为短 URL 长度主要是字符串切分与转换的开销空间复杂度O(N)N为已编码 URL 的数量所有原始 URL 都驻留在urls切片中碰撞风险无下标全局唯一递增互逆性必然成立decode(encode(x))恒等于x两个值得注意的边界非法短码会 panicdecode中strconv.Atoi的错误被直接丢弃i, _ : ...且没有对下标越界做检查。若传入非数字结尾或超出数组长度的短 URL会得到 0 值下标或触发越界。在 OJ 场景下输入总是由自己的encode产生因此不会触发但若要做成真实线上服务应补充错误处理。内存只增不减所有 URL 常驻内存短码永不复用。这是「以空间换简单」的典型取舍适合本题但不符合真实 TinyURL 服务对存储规模的预期。测试用例与本地验证仓库为本题提供了配套测试 535. Encode and Decode TinyURL_test.go核心逻辑如下func Test_Problem535(t *testing.T) { obj : Constructor() fmt.Printf(obj %v\n, obj) e : obj.encode(https://leetcode.com/problems/design-tinyurl) fmt.Printf(obj encode %v\n, e) d : obj.decode(e) fmt.Printf(obj decode %v\n, d) }测试流程完整覆盖了题目要求的调用链构造 Codec → encode 长 URL → 用返回的短 URL 调 decode并打印中间结果以便人工核对d与原始 URL 一致。这也印证了 README 代码末尾注释中的三段式使用契约。本地运行方式在仓库根目录下# 运行本题的测试 go test -v ./leetcode/0535.Encode-and-Decode-TinyURL/... # 运行全部题解并生成覆盖率对应仓库 gotest.sh 的写法 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...模块名定义在 go.modgithub.com/halfrost/LeetCode-GoGo 1.19每个题解目录都是leetcode包的一部分因此可以直接用go test定位到本目录执行。项目描述的「100% test coverage」正是通过上述-coverprofile方式统计的。扩展思考真实 TinyURL 服务的其他编码方案下标索引法在本题中是最简解法但它把短码长度与「已编码数量」直接挂钩第 1 亿个 URL 的短码是 8 位数字且短码可被轻易遍历不适合真实生产环境。作为设计层面的延伸不属于本仓库实现常见的替代方向包括方案核心思路典型取舍Base62 短码把自增 ID 用 62 进制0-9a-zA-Z表示短码更紧凑仍需 ID 生成器短码可枚举哈希截断对长 URL 取哈希如 MD5/SHA 摘要并截取固定长度存在碰撞需加冲突检测与重试随机短码随机生成固定长度字符串写入存储前查重需要数据库唯一索引兜底无论采用哪种方案decode侧都必须能通过短码唯一定位原始 URL——这正是本题「保证互逆」约束在真实设计中的落点。理解了本题的下标映射思想再去看任何短码生成策略本质都是在回答同一个问题如何把一个短码稳定地映射回唯一的原始 URL。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考