C++12ms Clean Solution, Beats 83% Submissions


  • 0
    class Solution {
    public:
      bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        if (!m || !word.size())
          return false;
        int n = board.front().size();
        if (!n)
          return false;
        vector<vector<bool>> mark(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
          for (int j = 0; j < n; ++j)
          _exist(board, m, n, i, j, mark, word, 0);
        return res;
      }
        
      void _exist(vector<vector<char>>& board, int m, int n, int i, int j, vector<vector<bool>>& mark, string& word, int index) {
        if (res)
          return;
        if (!mark[i][j] && board[i][j] == word[index]) {     //not mark && match
          mark[i][j] = true;
          index++;
          if (index >= word.size() ) {
            res = true;
            return;
          }
          if (i - 1 >= 0) _exist(board, m, n, i - 1, j, mark, word, index); //up
            
          if (i + 1 < m) _exist(board, m, n, i + 1, j, mark, word, index); //down
            
          if (j - 1 >= 0) _exist(board, m, n, i, j - 1, mark, word, index); //left
           
          if (j + 1 < n) _exist(board, m, n, i, j + 1, mark, word, index); //right
          mark[i][j] = false;
        }
      }
    private:
      bool res = false;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.