c++ - 为什么这个解决方案在给定的测试用例上提供 TLE？

问题描述

问题链接：https ://leetcode.com/problems/word-search/

给定一个 2D 棋盘和一个单词，找出该单词是否存在于网格中。

单词可以由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。同一个字母单元格不能多次使用。

我们不应该使用一个字符两次。

例子：

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

约束：

board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

我的逻辑：在函数存在时，每当我在二维数组中找到给定字符串（字符串 s）的第一个字符时，我都会在其位置调用 DFS，以检查是否可以形成字符串。

我在提到的测试用例上得到了 TLE

测试用例：

[["a","a","a","a"],["a","a","a","a"],["a","a","a","a"],["a","a","a","a"],["a","a","a","b"]]
"aaaaaaaaaaaaaaaaaaaa"

预期输出：

true

代码：

class Solution {
public:
    
    bool dfs( vector<vector<char>> board , string s, int p ,int i , int j ){

        if( p == s.length() ){
            return true;
        }
        
        if( i < 0 || i >= board.size() || j < 0 || j >= board[i].size() || board[i][j] != s.at(p) ){
            return false;
        }
        
        char t = board[i][j];
        board[i][j] = ' ';
        
        bool res = dfs( board, s, p + 1 , i + 1, j ) | dfs( board, s, p + 1 , i - 1, j ) |
            dfs( board, s, p + 1 , i , j + 1 ) | dfs( board, s, p + 1 , i, j - 1 );
        
        board[i][j] = t;
        
        return res;
        
    }
    
    bool exist(vector<vector<char>>& board, string s) {
        
        for( int i = 0; i < board.size(); i++ ){
            for( int j = 0; j < board[0].size(); j++ ){
                if( board[i][j] == s.at(0) && dfs( board , s , 0, i , j ) ){
                    return true;
                }
            }
        }
        return false;
    }
};

提交详情：https ://leetcode.com/submissions/detail/398643848/

标签： c++depth-first-search

c++ - 为什么这个解决方案在给定的测试用例上提供 TLE？

问题描述

解决方案

推荐阅读