LeetCode 79单词搜索：回溯法多递归终止及效率差异问询

一、找到目标单词后立即终止所有递归的方法 #

你当前实现的backtrack版本已经通过**引用传递的全局标志位result**实现了高效终止逻辑：

• 当任意递归分支找到完整单词时，会将result设为true
• 所有后续递归步骤在执行分支前都会检查!result，一旦result为true，直接跳过所有方向的分支调用，快速回溯退出
• 上层递归也会因为result为true，不再执行剩余分支，实现全递归栈的立即终止

另外，类似backtrack_v2用or运算符的短路特性也能终止当前层级的后续分支，但这种方式无法像全局标志位一样让所有上层递归提前感知结果，且回溯时仍需执行map_been的还原操作，终止效率略低。

二、两个回溯版本的效率差异原因 #

backtrack比backtrack_v2快20%的核心原因在于更早终止无效递归、减少冗余操作：

1. 全局状态感知的提前终止

   • backtrack通过引用传递result，一旦某个分支找到目标，所有递归层级都会立即感知到这个状态，跳过后续所有分支调用，避免了大量无效的递归函数进入和执行
   • backtrack_v2的短路逻辑仅作用于当前层级的or运算，虽能停止当前层级的后续分支，但无法阻止上层递归中已经发起的调用，且部分递归仍会执行完整的入口检查（边界、字符匹配等）

2. 冗余检查的减少

   • backtrack在base case中，若result已经为true，会直接返回，无需执行字符匹配、标记位操作等冗余逻辑
   • backtrack_v2每次进入函数都要执行完整的边界检查、字符匹配判断，即使全局已经找到结果，部分递归调用仍会执行这些无效检查

3. 分支调用的前置过滤

   • backtrack在每个方向的递归调用前，都会先判断!result，仅在未找到结果时才执行分支，从根源上减少无效调用
   • backtrack_v2的分支调用依赖or的短路特性，虽然后续分支不会执行，但前序分支的调用已经触发了函数入口的所有检查

完整实现代码 #

class Solution
{
private:
    vector<vector<char>> matrix;            
    string word;

bool backtrack (int row, int col, int N,
                const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been, bool& result)
    {
        if (word[N]==matrix[row][col])                                                  
            {
                if (N==word_size or result)                                             
                    return result = true;

                map_been[row][col] = true;

                if (!result and col!=num_cols and map_been[row][col+1]==0)              
                    backtrack(row, col+1, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and row!=num_rows and map_been[row+1][col]==0)              
                    backtrack(row+1, col, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and col!=0 and map_been[row][col-1]==0)                     
                    backtrack(row, col-1, N+1, num_rows, num_cols, word_size, map_been, result);

                if (!result and row!=0 and map_been[row-1][col]==0)                     
                    backtrack(row-1, col, N+1, num_rows, num_cols, word_size, map_been, result);

                map_been[row][col] = false;
            }

        return result;
    }

bool backtrack_v2 (int row, int col, int N, const int num_rows, const int num_cols, const int word_size, vector<vector<bool>>& map_been)
    {
        if (row<0 or row>num_rows or col<0 or col>num_cols or word[N]!=matrix[row][col] or map_been[row][col]==true)
            return false;

        if (N==word_size)                                   
            return true;

        map_been[row][col] = true;
        bool result =  backtrack_v2(row, col+1, N+1, num_rows, num_cols, word_size, map_been)       
                    or backtrack_v2(row+1, col, N+1, num_rows, num_cols, word_size, map_been)       
                    or backtrack_v2(row, col-1, N+1, num_rows, num_cols, word_size, map_been)       
                    or backtrack_v2(row-1, col, N+1, num_rows, num_cols, word_size, map_been);      
        map_been[row][col] = false;

        return result;
    }


public:
bool exist(vector<vector<char>>& matrix, string word)
    {
        int num_rows = matrix.size();
        int num_cols = matrix[0].size();
        int word_size = word.size();
        vector<vector<bool>> map_been (num_rows, (vector<bool> (num_cols, false)));             
        bool result=false;

        this->matrix = matrix;
        this->word = word;

        if (word_size> num_rows*num_cols)
            return false;

        for (int i=0; i<num_rows; i++)
            for (int j=0; j<num_cols; j++)
            {
                if (backtrack(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been, result))
                    return true;

                // if (backtrack_v2(i, j, 0, num_rows-1, num_cols-1, word_size-1, map_been))
                //     return true;
            }

        return false;
    }
};

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