LeetCode单词搜索近似C++代码为何一个TLE一个击败93%提交

首先明确结论：循环展开不是解法2性能优异的唯一原因。两种写法的渐近时间复杂度确实完全一致，但递归核心路径上叠加的多重开销差，会被指数级的递归调用次数放大，最终形成TLE和击败93%提交的巨大差距。被忽略的性能影响点主要有三个：

1. 方向vector的运行时开销远大于“常数级”预期 #

解法1中用二维vector存储四个方向偏移量的写法，本身就带多重额外开销：

• 若dir vector定义在递归函数内部，每次进入递归都会触发vector的构造、析构，涉及堆内存的申请释放，单这一项的开销就比硬编码写法高一个数量级。
• 即便将dir定义为全局/静态常量，范围for遍历vector本质是迭代器遍历，每次循环都要执行迭代器自增、迭代器边界校验、偏移量内存寻址取值的操作，这些指令在单轮递归里看起来不起眼，但单词搜索最坏情况递归调用量级可达O(M*N*3^L)（M、N为矩阵长宽，L为目标单词长度），总开销会被放大几十万到上百万倍。
• 解法2的硬编码偏移量是编译期就确定的常量，CPU执行时直接从寄存器取立即数即可，完全不需要走内存寻址，也没有任何容器相关的额外开销。

2. ||短路逻辑的剪枝效率更高 #

这是很多人完全没注意到的核心差异，不属于循环展开的范畴：

• 解法2用||运算符串联四个方向的递归调用时，只要任意一个方向的递归返回true，后续方向的调用会被直接短路，连对应的函数调用指令都不会执行，剪枝没有任何多余损耗。
• 解法1的循环遍历写法，哪怕在循环体内写了if (dfs(...) return true;的即时返回逻辑，每次取方向、判断循环边界的控制流开销依然存在；如果写法稍有问题，没有在拿到true结果时立刻跳出循环，甚至会出现无意义的多余递归调用，开销直接翻数倍。

3. 编译器的优化空间存在量级差距 #

两种写法给编译器的优化空间完全不在一个层级：

• 硬编码四个递归调用的写法，所有控制流在编译期完全确定，编译器可以非常轻松地完成函数内联、寄存器分配、栈帧消冗等优化，最终生成的汇编代码冗余度极低。
• 带vector遍历的写法涉及动态容器访问、迭代器操作，编译器无法确认vector内容是否会被意外修改，很难做到极致的循环展开和分支优化，甚至会默认插入不少容器边界校验指令，最终生成的代码效率远低于硬编码版本。

回溯类题目很容易给人“只要渐近复杂度对了就能过”的错觉，但实际上递归核心路径上每多一次内存访问、每多一个多余分支，都会被指数级的调用量放大。单轮递归差10个时钟周期，1e7次调用就会差出0.1秒以上的总耗时——这刚好就是OJ平台上卡线TLE和高排名提交的典型差距，根本不是所谓“微不足道的常数优化”。

内容的提问来源于stack exchange，提问作者Ramasamy Kandasamy