字符串综合
本节目标
把方向状态、定长窗口、格式分配和前缀匹配组合成字符串综合题的稳定解法。
综合题不一定依赖更高级的数据结构，难点往往是把基础模板放进更严格的状态更新顺序。本节四道题分别训练方向切换、按词长分组的窗口、精确格式构造和 Trie 最短前缀查询。
识别信号
遇到以下特征，可以优先从本节的四类模型入手：
- 扫描方向会在固定边界反转，输出由多条轨迹重新拼接；
- 所有待匹配单词等长，目标子串必须由这些单词首尾相接组成；
- 输出宽度固定，需要把剩余空间按规则分配到若干间隙；
- 字典中保存的是前缀，希望为每个单词找到最短有效词根。
问题模型与核心不变量
- 方向模拟：
row表示当前写入行，direction只在首行和末行改变。 - 定长窗口：左右边界始终落在同一个词长余数类中，窗口只按一个单词移动。
- 文本对齐：先确定一行能放哪些单词，再分配空格；选词和排版不能混在一起。
- 最短词根：沿 Trie 查询时，第一个结束标记就是答案，继续向下反而会得到更长词根。
这些不变量的共同点是：先确定“状态何时有效”，再规定一次移动后必须更新哪些量。
通用模板
确定最小处理单位：字符、等长单词、整行或 Trie 节点
定义当前状态与合法边界
按题目规则推进一个单位
一旦触及边界、频次上限或结束标记，立即完成对应动作
最后统一拼接或返回结果
不要一边扫描一边临时修补输出格式。状态转移和答案构造分层后，边界会清楚得多。
模板变体
- 方向状态既可以用
+1/-1表示，也可以用布尔值表示向下或向上。 - 等长单词窗口需要按
0..wordLength-1分组；普通字符窗口不需要这一步。 - 空格分配可以写成“基础份额＋左侧余数”，最后一行则固定左对齐。
- Trie 查询可以返回最短词根、最长已有前缀或是否存在完整单词；停止条件随任务改变。
母题序列
以下题目按拓展顺序学习：
前两题强调移动状态，后两题强调构造规则。四题都要求把边界条件直接写进状态定义，而不是留到循环结束后补救。
常见误区
- 行数为一时仍然切换方向，造成下标越界。
- 把所有起点混进同一个定长窗口，破坏词边界。
- 文本对齐时把多余空格分给右侧，或把最后一行也做两端对齐。
- Trie 中找到完整词根后继续搜索，返回了更长而不是最短的根。
- 只验证样例，没有用暴力结果检查窗口算法的频次与重叠边界。
迁移方向
方向切换可以迁移到蛇形遍历和往返模拟；按余数分组可以迁移到其他固定块长窗口；商与余数分配适用于分页和资源均分；最短前缀查询可以迁移到路径压缩、词典归一化和前缀路由。
掌握这些模型后，综合题的关键不再是记住长代码，而是识别最小处理单位和必须始终成立的不变量。