leetcode Word Search 待解决？

终于搞定了这个DFS，最近这个DFS写的很不顺手，我一直以为递归这种东西只是在解重构时比较麻烦，现在看来，连最简单的返回true和false的逻辑关系都不能说one hundred present 搞定。

人品啊TLE:

 class Solution {

 public:

 bool legal(int i, int j, vector<vector<char>> board)

 {

     if (i >=  && i < board.size() && j >=  && j < board[i].size())

         return true;

     return false;

 }

    bool dfs(vector<vector<char>>& board, string word, int t, int i, int j, vector<vector<bool>> visited)

 {

     if (t == word.length())

         return true;

     if (board[i][j] == word[t])

     {

         visited[i][j] = true;

         if (legal(i - , j, board) && !visited[i - ][j] && dfs(board, word, t + , i - , j, visited))

             return true;

         if (legal(i, j + , board) && !visited[i][j + ] && dfs(board, word, t + , i, j + , visited))

             return true;

         if (legal(i + , j, board) && !visited[i + ][j] && dfs(board, word, t + , i + , j, visited))

             return true;

         if (legal(i, j - , board) && !visited[i][j - ] && dfs(board, word, t + , i, j - , visited))

             return true;

     }

     visited[i][j] = false;

     return false;

 }

 bool exist(vector<vector<char>>& board, string word)

 {

     int m = board.size();

     int n = board[].size();

     vector<vector<bool>> visited(m, vector<bool>(n, false));

     for (int i = ; i < board.size(); i++)

     {

         for (int j = ; j < board[].size(); j++)

         {

             if (dfs(board, word, , i, j, visited))

                 return true;

         }

     }

     return false;

 }

 };

为什么？

下面的依然是超时的，无论怎么尝试都是超时的，觉得和提交的AC代码并没有什么区别啊？

 #include<iostream>

 #include<vector>

 using namespace std;

 bool isLegal(int i, int j, vector<vector<char>> board)

 {

     int H = board.size();

     int L = board[].size();

     if (i >=  && i < H&&j >=  && j < L)

         return true;

     return false;

 }

 bool searchWord(vector<vector<char>> board, vector<vector<bool>> visited, string word, int i, int j, int index)

 {

     if (index >= word.length())

     {

         return true;

     }

     /*if (word[index] == board[i][j])

     {*/

         visited[i][j] = true;

         int dx[] = { , , -,  };

         int dy[] = { , , , - };

         for (int x = ; x < ; ++x)

         {

             int ii = i + dx[x];

             int jj = j + dy[x];

             if (isLegal(ii, jj, board) && !visited[ii][jj] && board[ii][jj] == word[index] && searchWord(board, visited, word, ii, jj, index + ))

                 return true;

         }

         /*if (isLegal(i - 1, j, board) && !visited[i - 1][j] && board[i - 1][j]==word[index] && searchWord(board, visited, word, i - 1, j, index + 1))

             return true;

         if (isLegal(i, j - 1, board) && !visited[i][j - 1] && board[i][j - 1] == word[index] && searchWord(board, visited, word, i, j - 1, index + 1))

             return true;

         if (isLegal(i + 1, j, board) && !visited[i + 1][j] && board[i + 1][j] == word[index] && searchWord(board, visited, word, i + 1, j, index + 1))

             return true;

         if (isLegal(i, j + 1, board) && !visited[i][j + 1] && board[i][j + 1] == word[index] && searchWord(board, visited, word, i, j + 1, index + 1))

             return true;*/

     /*}*/

     visited[i][j] = false;

     return false;

 }

 bool exist(vector<vector<char>>& board, string word) {

     if (word.empty()) return false;

     int H = board.size();

     int L = board[].size();

     int i, j;

     vector<vector<bool>> visited(H, vector<bool>(L, false));

     for (i = ; i < H; i++)

     {

         for (j = ; j < L; j++)

         {

             if (word[]==board[i][j]&&searchWord(board, visited, word, i, j, ))

             {

                 return true;

             }

         }

     }

     return false;

 }

 int main()

 {

     char boardArray[][] =

     {

         { 'A', 'B', 'C', 'E' },

         { 'S', 'F', 'C', 'S' },

         { 'A', 'D', 'E', 'E' }

     };

     vector<vector<char>> board1();

     for (int i = ; i < ; i++)

     {

         vector<char> temp();

         temp[] = 'A';

         board1[i] = temp;

         for (int j = ; j < ; j++)

         {

             board1[i][j] = boardArray[i][j];

         }

     }

     if (exist(board1, "ABCCED"))

         cout << <<endl;

     else

         cout <<  << endl;

 }

巴特西

leetcode Word Search 待解决？

最新文章

热门文章