为什么我的代码在leetcode中效果很好，而我的代码给出时间限制？

Question

ref： https://leetcode.com/problems/problems/word-word-word-word-word-word-搜索/提交/

简短的问题语句：给出了字符和字符串的矩阵，该字符串是否存在于此矩阵中。请参阅上述链接以获取详细信息。

solution-1 给出超过时间限制。

class Solution {
public:
    int n;
    int m;
    bool search(vector<vector<char>>& board, const char* w, int i, int j){
        
        if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
        if(*(w+1) == '\0') return true;

        char t = board[i][j];
        board[i][j] = '\0';
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(auto d: dir){
            bool temp = search(board, w+1, i + d[0], j + d[1]);
            if(temp) return true;
        }
        board[i][j] = t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
};

解决方案2 正常工作。实际上，比C ++提交的〜93％快

class Solution {
public:
    int n;
    int m;
    bool search(vector<vector<char>>& board, const char* w, int i, int j){
        
        if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
        if(*(w+1) == '\0') return true;

        char t = board[i][j];
        board[i][j] = '\0';
        if(search(board, w+1, i -1, j) || search(board, w+1, i+1, j) || search(board, w+1, i, j-1) || search(board, w+1, i, j+1)) return true;
        board[i][j] = t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
};

这两个解决方案之间的唯一区别是我在搜索功能中递归称呼搜索功能的方式。

在解决方案1 ​​中，它是：

vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(auto d: dir){
    bool temp = search(board, w+1, i + d[0], j + d[1]);
    if(temp) return true;
}

在 solude-2 中，它是：

if(search(board, w+1, i -1, j) || search(board, w+1, i+1, j) || search(board, w+1, i, j-1) || search(board, w+1, i, j+1)) return true;

我认为第二个解决方案就像循环展开，而这部分解释了为什么第二个解决方案比第二个解决方案更快地第一个。这不是只有一个恒定的因素而更快。我的意思是渐近，它们是相似的。我感到惊讶的是，循环展开导致我的解决方案从TLE转变到93％的解决方案。

基本上，我的问题是，循环展开第二个解决方案如此之快的唯一原因，还是我缺少某些东西？

Answer 1

我不确定auto类型的时间复杂性！但是，如果您从递归函数中删除了2D矢量构造，而不是auto使用基于普通索引的循环访问向量，则您将通过TimeLimit。

class Solution {
public:
    int n;
    int m;
    vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool search(vector<vector<char>>& board, const char* w, int i, int j){
        
        if(i < 0 || i >= m || j < 0 || j >= n || *w != board[i][j] || board[i][j] == '\0') return false;
        if(*(w+1) == '\0') return true;

        char t = board[i][j];
        board[i][j] = '\0';
        
        for(int r=0; r<4; r++){
            bool temp = search(board, w+1, i + dir[r][0], j + dir[r][1]);
            if(temp) return true;
        }
        board[i][j] = t;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(search(board, word.c_str(), i, j)) return true;
            }
        }
        return false;
    }
};