企业官网建设流程全解析

• 示例工程

本篇文章以 type-challenges 仓库中编号 14188 的 hard 级挑战 Run-length encoding 为研究对象，完整剖析如何在 TypeScript 类型系统中用模板字面量类型与递归实现游程编码（Run-length Encoding）的编码器Encode<S>与解码器Decode<S>。读完本文，你将掌握类型级字符串逐字符拆解、连续字符分组计数、数字串读取与字符重复展开的完整套路，并能举一反三应用到仓库中其他字符串处理类挑战（如 Split、DropChar、PercentageParser 等）。

一、题目速览：14188 Run-length encoding

该挑战位于仓库 questions/14188-hard-run-length-encoding，由 Hen Hedymdeith（GitHub 账号 @alfaproxima）提出，在 info.yml 中标记的难度为hard。

原文档给出的需求非常精炼，原文如下：

Given astringsequence of a letters f.e.AAABCCXXXXXXY. Return run-length encoded string3AB2C6XY. Also make a decoder for that string.

即：给定一个由字母组成的字符串序列，返回其游程编码（Run-length encoded）字符串；同时还需要为该编码串实现解码器。文档给出的唯一一组编码/解码示例为：

需要在 template.ts 中补齐的类型签名如下：

namespace RLE { export type Encode<S extends string> = any export type Decode<S extends string> = any }

对应的测试用例定义在 test-cases.ts 中：

import type { Equal, Expect } from '@type-challenges/utils' type cases = [ // Raw string -> encoded string Expect<Equal<RLE.Encode<'AAABCCXXXXXXY'>, '3AB2C6XY'>>, // Encoded string -> decoded string Expect<Equal<RLE.Decode<'3AB2C6XY'>, 'AAABCCXXXXXXY'>>, ]

二、先把游程编码的规则读透

在动手写类型之前，必须先把字符串层面的算法规则弄清楚，否则类型实现的每一步都会出错。

把AAABCCXXXXXXY从左到右扫描，按"连续相同字符"分组：

拼接得到3AB2C6XY。可见本挑战的规则是：

1. 连续出现 ≥ 2 次的字符：编码为「出现次数（十进制数字串）+ 字符」，如AAA → 3A、CC → 2C、XXXXXX → 6X；
2. 仅出现 1 次的字符：原样输出，不加数字前缀，如B → B、Y → Y。

解码是编码的逆过程：遇到数字前缀N时，将紧随其后的单个字符展开N次；没有数字前缀的字符直接透传。因此3AB2C6XY展开为AAA + B + CC + XXXXXX + Y = AAABCCXXXXXXY。

两个值得注意的工程细节（虽然测试用例没有覆盖，但设计类型时应心中有数）：

• 数字前缀可以是多位数（例如12X表示 12 个X），解码器应能完整读取整段数字，而不是只读一位；
• 数字前缀后的字符按题意总是存在的，但实现时可以决定对"数字后无字符"这类非法输入采取何种策略（本文采用返回never的保守做法）。

三、类型级字符串处理的基础设施

要实现这个挑战，需要用到 TypeScript 类型系统中两个最核心的"字符串处理"能力：模板字面量类型与infer 递归。它们在本仓库中是一系列字符串类挑战的共同基础设施，例如：

• 02822-hard-split：用分隔符切分字符串，其核心同样是S extends${infer Head}${infer Tail}`` 式的逐字符递归；
• 02070-medium-drop-char：删除字符串中的指定字符；
• 00298-medium-length-of-string：用元组计数统计字符串长度；
• 00119-medium-replaceall：全局替换子串；
• 01978-medium-percentage-parser：解析百分号字符串中的数字与符号，同样涉及"读取数字串"的类型逻辑。

下面简述本挑战将用到的三个基本功。

1. 逐字符拆分：infer+ 模板字面量

type SplitHead<S extends string> = S extends `${infer Head}${infer Tail}` ? [Head, Tail] // 例如 'ABC' -> ['A', 'BC'] : never

模板字面量类型里的infer Head默认匹配一个字符，infer Tail匹配剩余部分。当字符串为空时，条件不成立，从而形成递归的终止分支。

2. 条件判断：某字符是否为数字

type IsDigit<C extends string> = C extends `${number}` ? true : false

TS 内置的${number}模板类型可以匹配任何合法的十进制数字表示。单个数字字符（0~9）都能匹配成功，而字母字符不会。

3. 用元组长度做"计数"

类型系统里没有可变的number变量，计数通常借助元组的length属性：每"数一次"就往元组里追加一个元素，最终T['length']就是精确的字面量数字类型。例如统计字符串长度：

type LengthOf<S extends string, T extends string[] = []> = S extends `${string}${infer Rest}` ? LengthOf<Rest, [...T, string]> : T['length']

LengthOf<'AAA'>会精确地得到字面量类型3，进而${LengthOf<'AAA'>}得到'3'。这正是 Encode 中把"出现次数"写成数字前缀的手段。

四、实现 Encode：把连续字符折叠成游程

分步拆解

编码过程可以分解为三个子问题：

1. 分组：从串首提取出连续相同字符构成的一段（如AAA），并得到剩余串；
2. 计段：统计该段的长度；若长度 ≥ 2 则带上数字前缀，否则原样输出该字符；
3. 递归：对剩余串重复上述过程。

参考实现

namespace RLE { // ── 1. 从 S 开头截取与 C 连续相同的字符段 ── // 返回 [连续段, 剩余串]，例如 TakeRun<'A', 'AAABCC'> -> ['AAA', 'BCC'] type TakeRun<C extends string, S extends string, Acc extends string = C> = S extends `${C}${infer Rest}` ? TakeRun<C, Rest, `${Acc}${C}`> : [Acc, S] // ── 2. 计算字符串的字面量长度 ── type Length<S extends string, T extends string[] = []> = S extends `${string}${infer Rest}` ? Length<Rest, [...T, string]> : T['length'] // ── 3. 根据连续段长度决定是否加数字前缀 ── // 'AAA' -> '3A'; 'B' -> 'B'; 'CC' -> '2C' type EncodeRun<C extends string, Run extends string> = Run extends `${C}${C}${string}` // 连续出现 >= 2 次 ? `${Length<Run>}${C}` : C // 只出现 1 次，原样输出 // ── 4. 编码主体：递归处理每一段 ── export type Encode<S extends string> = S extends `${infer C}${string}` ? TakeRun<C, S> extends [infer Run extends string, infer Rest extends string] ? `${EncodeRun<C, Run>}${Encode<Rest>}` : never : S }

逐行讲解

TakeRun是本实现的关键。它以首字符C为参照，只要剩余串仍以C开头就继续累积进Acc，直到遇到第一个不同的字符为止：

• 输入'AAABCCXXXXXXY'，首字符C = 'A'；
• 递归过程：Acc依次变为'A'→'AA'→'AAA'，遇到'B'后停止，返回['AAA', 'BCCXXXXXXY']。

EncodeRun用Run extends${C}${C}${string}`` 判断连续段是否至少 2 个字符。注意这里刻意没有直接比较长度数字，而是利用模板匹配：

• Run = 'AAA'能匹配"两个C再加任意内容" → 输出3A；
• Run = 'B'不能匹配 → 原样输出B；
• Run = 'CC'能匹配 → 输出2C。

之所以用模板匹配而不是Length<Run> extends 1之类的判断，是因为字面量长度的比较在类型层面更繁琐，模板匹配表达"至少两个字符"更加直接可靠。

Encode主循环：只要串非空，就取出首字符C，用TakeRun切出一段，把EncodeRun的结果与对剩余串递归的结果拼接。空串''无法匹配${infer C}${string}，直接返回自身，成为终止分支。

沿'AAABCCXXXXXXY'手工推演一遍完整流程：

Encode<'AAABCCXXXXXXY'> TakeRun<'A', ...> → ['AAA', 'BCCXXXXXXY'] EncodeRun<'A', 'AAA'> → '3A' + Encode<'BCCXXXXXXY'> → 'B' + Encode<'CCXXXXXXY'> → '2C' + Encode<'XXXXXXY'> → '6X' + Encode<'Y'> → 'Y' 结果：'3A' + 'B' + '2C' + '6X' + 'Y' = '3AB2C6XY' ✓

五、实现 Decode：把游程展开为原始串

分步拆解

解码同样拆成三个子问题：

1. 读数字：从串首连续读取数字位，直到遇到非数字字符，得到完整的十进制数字串N与剩余串；
2. 展开：把紧随数字之后的那个字符重复N次；
3. 递归：对剩余串继续解码；若当前字符不是数字，则原样透传并继续。

参考实现

namespace RLE { // ── 1. 从串首读取完整数字串 ── // ReadNum<'3AB2C6XY'> -> ['3', 'AB2C6XY']；ReadNum<'12X'> -> ['12', 'X'] type ReadNum<S extends string, Acc extends string = ''> = S extends `${infer D}${infer Rest}` ? D extends `${number}` ? ReadNum<Rest, `${Acc}${D}`> : [Acc, S] : [Acc, S] // ── 2. 把字符 C 重复 N 次（N 为十进制数字字符串）── // Repeat<'A', '3'> -> 'AAA' type Repeat< C extends string, N extends string, Acc extends string = '', Count extends string[] = [] > = `${Count['length']}` extends N ? Acc : Repeat<C, N, `${Acc}${C}`, [...Count, string]> // ── 3. 解码主体 ── export type Decode<S extends string> = S extends `${infer Head}${infer Tail}` ? Head extends `${number}` ? ReadNum<S> extends [infer N extends string, infer Rest extends string] ? Rest extends `${infer C}${infer _}` ? `${Repeat<C, N>}${Decode<Rest>}` : never // 非法输入：数字后没有字符 : never : `${Head}${Decode<Tail>}` : S }

逐行讲解

ReadNum逐位累积数字。Acc初始为空，每遇到一个数字字符就追加到Acc尾部；一旦遇到非数字字符，立即返回[Acc, S]（注意返回的是当前的完整剩余串S，而不是Rest，因为Rest在上一轮已被消费）。这样即使编码中出现12X这种多位数，也能一次性读出'12'。

Repeat是"用元组长度计数"的典型应用。Count每递归一次追加一个元素，比较${Count['length']}与目标数字串N：

• 相等 → 返回累积出的Acc（终止）；
• 不等 → 继续在Acc尾部追加一个C，同时Count加一。

以Repeat<'A', '3'>为例，递归过程为：'0'≠'3'→Acc='A'、Count=['']；'1'≠'3'→Acc='AA'、Count=['','']；'2'≠'3'→Acc='AAA'、Count=['','','']；'3'='3'→ 返回'AAA'。

Decode主循环先看当前字符Head：

• 是数字 → 用ReadNum读出完整数字串N，再从Rest中取出第一个字符C，用Repeat<C, N>展开，然后递归解码Rest（注意这里递归传入的是Rest，它仍然包含字符C本身，但Repeat已经消费了它，因此不会重复输出）；
• 不是数字 → 原样透传Head，对Tail继续递归；
• 空串 → 返回自身，终止。

沿'3AB2C6XY'手工推演：

Decode<'3AB2C6XY'> Head='3' 是数字 → ReadNum → N='3', Rest='AB2C6XY' C='A' → Repeat<'A','3'> = 'AAA' + Decode<'AB2C6XY'> → 'A' + Decode<'B2C6XY'> → 'B' + Decode<'2C6XY'> → Repeat<'C','2'> = 'CC' + Decode<'6XY'> → Repeat<'X','6'> = 'XXXXXX' + Decode<'Y'> → 'Y' 结果：'AAA' + 'A' + 'B' + 'CC' + 'XXXXXX' + 'Y' = 'AAABCCXXXXXXY' ✓

六、用仓库测试用例验证实现

test-cases.ts 中通过Equal与Expect两个工具类型对结果做编译期断言：

Expect<Equal<RLE.Encode<'AAABCCXXXXXXY'>, '3AB2C6XY'>> Expect<Equal<RLE.Decode<'3AB2C6XY'>, 'AAABCCXXXXXXY'>>

这两个工具定义在仓库 utils/index.d.ts 中。其中Equal的实现值得注意——它利用"同一泛型函数在不同实例化下是否可互相赋值"来检测两个类型是否结构上完全相同（而不是单向可赋值）：

export type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends (<T>() => T extends Y ? 1 : 2) ? true : false export type Expect<T extends true> = T

Expect<T extends true>强制断言必须是true字面量类型：一旦你的Encode/Decode推导结果与期望不一致，编译器就会在这一行报错。因此可以直接在本地执行tsc --noEmit（或直接在编辑器中打开test-cases.ts）来验证上面给出的实现是否正确通过这两个方向上的断言。

七、边界情况与健壮性讨论

从上面的实现出发，可以进一步确认它在以下边界输入下的行为：

• 空字符串：Encode<''>与Decode<''>均返回''。模板匹配${infer C}${string}/${infer Head}${infer Tail}对空串不成立，直接落入终止分支；
• 全是单字符的输入：例如Encode<'ABC'>→'ABC'，因为每段长度都是 1，EncodeRun均走原样输出分支；
• 多位数前缀：Decode<'12X'>可正确得到 12 个X，因为ReadNum会连续读取'1'与'2'拼成'12'；
• 非法输入（数字后无字符）：Decode<'3'>在Rest extends${infer C}${infer _}`` 分支失败，返回never。这是一种"显式拒绝"的策略，避免静默产出错误类型。

同时需要了解类型系统本身的限制（这属于实践中的常识，可从实现结构推断）：Repeat的递归层数等于目标数字的大小，Length与TakeRun的递归层数等于字符串长度，二者都会受到编译器递归深度上限的约束。对于本挑战测试用例这种几十个字符以内的字符串完全够用；若遇到极长输入，则要考虑用"翻倍展开"之类的技巧降低递归深度。

八、延伸：同一仓库中的类型级字符串挑战

掌握了本挑战的三大核心技巧——模板字面量拆解、infer递归、元组长度计数——你会发现仓库中大量字符串类挑战共享同一套思维模式：

九、小结

本文以 questions/14188-hard-run-length-encoding 为骨架，完整还原了在 TypeScript 类型系统中实现游程编码的全过程：

• 编码器Encode<S>：通过TakeRun对连续相同字符分组、Length+ 模板匹配判断是否需要数字前缀，最后递归拼接，把AAABCCXXXXXXY压缩为3AB2C6XY；
• 解码器Decode<S>：通过ReadNum完整读取数字前缀、Repeat用元组长度计数展开字符，把3AB2C6XY还原为AAABCCXXXXXXY。

两道类型都通过了 test-cases.ts 中基于 utils/index.d.ts 的Equal/Expect编译期断言。这套"模板字面量拆解 + infer 递归 + 元组计数"的组合拳，是攻克仓库内绝大多数 hard 级字符串挑战的通用武器。

• 示例工程