LeetCode单词搜索回溯代码传值超时、传引用通过原因求解

核心原因是C++值传递带来的额外深拷贝开销，具体分析如下：

• 当existsUtil函数的board参数使用值传递时，每次调用该函数都会对整个二维网格做深拷贝，单次拷贝的时间复杂度为O(mn)，m、n分别为网格的行数和列数，网格越大拷贝开销越高。
• 本题DFS的最坏递归调用次数约为O(mn * 3^k)，k为目标单词的长度：每个网格格子都可以作为搜索起点，每一步递归除了来路方向外有3个可选方向，最多递归k层。
• 两者叠加后总时间复杂度会从原本设计的O(mn * 3^k)暴涨到O( (mn)^2 * 3^k )，大输入下拷贝产生的额外开销会直接占满时间限制，触发TLE。

改为引用传递后性能大幅提升的原因：

• vector<vector<char>> &board是引用传递，函数操作的是原始网格的内存地址，不会产生任何拷贝开销，总时间复杂度回到原本的设计量级，因此可以通过所有测试用例。
• 注意：引用传递时所有递归分支共享同一个网格，必须保留board[i][j] = temp的回溯操作，否则前一个搜索分支修改的网格状态会干扰后续分支的搜索，导致结果错误。而你原来值传递的版本中每个递归分支都有独立的网格副本，回溯操作实际是多余的，只是巨大的拷贝开销掩盖了这个小问题。

内容的提问来源于stack exchange，提问作者Vedant Jadhav