My C++ AC solution with explanation (DFS).


  • 0
    M

    Maybe my solution is not concise enough and, frankly speaking, it got 230ms. But I think it is clear and easy to understand.

    #include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution {
      typedef vector<vector<char> > BOARD;
      struct POS {
        size_t x, y;
        POS() = default;
        POS(size_t _x, size_t _y):x(_x),y(_y){}
      };
      private:
    
      /* Get all the legal moves based on current position */
      vector<POS> legal_pos(BOARD const& board, POS const& current) {
        vector<POS> result;
        if (current.x != 0 && board[current.y][current.x-1] != 0)
          result.push_back(POS(current.x-1, current.y));
        if (current.x < board[0].size()-1 && board[current.y][current.x+1] != 0)
          result.push_back(POS(current.x+1, current.y));
        if (current.y != 0 && board[current.y-1][current.x] != 0)
          result.push_back(POS(current.x, current.y-1));
        if (current.y < board.size()-1 && board[current.y+1][current.x] != 0)
          result.push_back(POS(current.x, current.y+1));
        return result;
      }
      
      /* The recursion part (DFS)*/
      bool r_exist(BOARD& board, string const& word, size_t target, POS const& current) {
        if (target == word.size()) return true;
        bool result = false;
        auto next_moves = legal_pos(board, current); // Get legal moves
        for (auto pos : next_moves) {
          if (board[pos.y][pos.x] == word[target]) {
            char removed_element = board[pos.y][pos.x];
            board[pos.y][pos.x] = 0; // Mark current element as visited
            result = r_exist(board, word, target+1, pos);
            board[pos.y][pos.x] = removed_element; // Restore the current element
            if (result) break;
          }
        }
        return result;
      }
    
      public:
    
      /* Method interface */
      bool exist(vector<vector<char> > &board, string word) {
        if (word.size() == 0) return true;
        if (board.size() == 0 || board[0].size() == 0) return false;
    
        // Find all the possible start position
        vector<POS> start_pos;
        for (size_t y = 0; y < board.size(); y++) {
          for (size_t x = 0; x < board[0].size(); x++) {
            if (board[y][x] == word[0])
              start_pos.push_back(POS(x,y));
          }
        }
    
        // Iterate through all the possible start position
        bool result = false;
        for (auto pos : start_pos) {
          char removed_element = board[pos.y][pos.x];
          board[pos.y][pos.x] = 0;
          result = r_exist(board, word, 1, pos);
          board[pos.y][pos.x] = removed_element;
          if (result) break;
        }
        return result;
      }
    };

Log in to reply
 

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