# 79. Word Search
Difficulty: Medium

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-08-28
**/
#include <cstdlib>
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define VERSION_1 0
#define VERSION_2 0
#define VERSION_3 1

struct TestCaseStruct {
  struct Input {
    vector<vector<char>> board;
    string word;
  } input;
  bool expected_output;
};

#if VERSION_1
struct Position {
  Position(int i, int j) {
    this->i = i;
    this->j = j;
    this->next_direction = 0;
  }

  Position(int i, int j, int next_direction) {
    this->i = i;
    this->j = j;
    this->next_direction = next_direction;
  }
  int i;
  int j;
  int next_direction;
};

// non-recursive, but with BUG
class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    vector<vector<int>> used(board.size(), vector<int>(board[0].size(), 0));
    for (int i = 0; i < board.size(); ++i) {
      for (int j = 0; j < board[i].size(); ++j) {
        size_t index = 0;
        if (board[i][j] == word[index++]) {
          used[i][j] = 1;
          stack<Position> s;
          s.emplace(Position(i, j, -1));
          while (index < word.size()) {
            auto current_index = index;
            auto& current_position = s.top();
            ++current_position.next_direction;
            Position adjecent[] = {
                {current_position.i - 1, current_position.j},
                {current_position.i, current_position.j + 1},
                {current_position.i + 1, current_position.j},
                {current_position.i, current_position.j - 1}};
            for (int next_direction = current_position.next_direction;
                 next_direction < 4; ++next_direction) {
              const auto& next = adjecent[next_direction];
              if (next.i < 0 || next.i >= board.size() || next.j < 0 ||
                  next.j >= board[i].size()) {
                continue;
              }
              if (used[next.i][next.j] == 1 ||
                  board[next.i][next.j] != word[index]) {
                continue;
              }
              used[next.i][next.j] = 1;
              s.emplace(Position(next.i, next.j, -1));
              ++index;
              break;
            }
            if (index == current_index) {
              used[current_position.i][current_position.j] = 0;
              --index;
              s.pop();
              if (s.empty()) {
                break;  // break "while (index < word.size())"
              }
            }
          }
          if (index == word.size()) {
            return true;
          }
          used[i][j] = 0;
        }
      }
    }
    return false;
  }
};
#endif

#if VERSION_2
struct Point {
  Point(int i, int j) {
    this->i = i;
    this->j = j;
  }

  int i;
  int j;
};

class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    // board is m*n
    m_ = board.size();
    n_ = board[0].size();

    word_size_ = word.size();

    Point current_point(0, 0);
    for (current_point.i = 0; current_point.i < m_; ++current_point.i) {
      for (current_point.j = 0; current_point.j < n_; ++current_point.j) {
        size_t word_index = 0;
        if (board[current_point.i][current_point.j] == word[word_index]) {
          if (FindRecursively(board, word, current_point, word_index)) {
            return true;
          }
        }
      }
    }

    return false;
  }

 private:
  bool FindRecursively(vector<vector<char>>& board, const string& word,
                       Point current_point, size_t word_index) {
    if (++word_index >= word_size_) {
      return true;
    }

    char current_point_symbol = board[current_point.i][current_point.j];
    board[current_point.i][current_point.j] = '\0';
    vector<Point> adjecent_points = {{current_point.i - 1, current_point.j},
                                     {current_point.i, current_point.j + 1},
                                     {current_point.i + 1, current_point.j},
                                     {current_point.i, current_point.j - 1}};
    for (const auto& point : adjecent_points) {
      /*if (point.i < 0 || point.i >= m_ || point.j < 0 || point.j >= n_) {
        continue;
      }
      if (board[point.i][point.j] == '\0' ||
          board[point.i][point.j] != word[word_index]) {
        continue;
      }
      if (FindRecursively(board, word, point, word_index)) {
        return true;
      }*/
      if ((point.i >= 0 && point.i < m_ && point.j >= 0 && point.j < n_) &&
          board[point.i][point.j] != '\0' &&
          board[point.i][point.j] == word[word_index]) {
        if (FindRecursively(board, word, point, word_index)) {
          board[current_point.i][current_point.j] = current_point_symbol;
          return true;
        }
      }
    }

    board[current_point.i][current_point.j] = current_point_symbol;
    return false;
  }

  // board is m*n
  size_t m_;
  size_t n_;
  size_t word_size_;
};
#endif

#if VERSION_3
struct Point {
  Point(int i, int j) {
    this->i = i;
    this->j = j;
  }

  int i;
  int j;
};

class Solution {
 public:
  bool exist(vector<vector<char>>& board, string word) {
    // board is m*n
    m_ = board.size();
    n_ = board[0].size();

    Point current_point(0, 0);
    for (current_point.i = 0; current_point.i < m_; ++current_point.i) {
      for (current_point.j = 0; current_point.j < n_; ++current_point.j) {
        const char* w = word.c_str();
        if (board[current_point.i][current_point.j] == *w) {
          if (FindRecursively(board, w, current_point)) {
            return true;
          }
        }
      }
    }

    return false;
  }

 private:
  bool FindRecursively(vector<vector<char>>& board, const char* w,
                       const Point& current_point) {
    if (*(++w) == '\0') {
      return true;
    }

    char current_point_symbol = board[current_point.i][current_point.j];
    board[current_point.i][current_point.j] = '\0';
    vector<Point> adjecent_points{{current_point.i - 1, current_point.j},
                                  {current_point.i, current_point.j + 1},
                                  {current_point.i + 1, current_point.j},
                                  {current_point.i, current_point.j - 1}};
    for (const auto& point : adjecent_points) {
      if ((point.i >= 0 && point.i < m_ && point.j >= 0 && point.j < n_) &&
          board[point.i][point.j] != '\0' && board[point.i][point.j] == *w) {
        if (FindRecursively(board, w, point)) {
          board[current_point.i][current_point.j] = current_point_symbol;
          return true;
        }
      }
    }

    board[current_point.i][current_point.j] = current_point_symbol;
    return false;
  }

  // board is m*n
  size_t m_;
  size_t n_;
};
#endif

int main(int argc, char* argv[]) {
  /*
    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.

    board2 =
    [
      ['a', 'b'],
      ['c', 'd']
    ]
    Given word = "dbac", return true.

    [["b","a","a","b","a","b"],
		 ["a","b","a","a","a","a"],
		 ["a","b","a","a","a","b"],
		 ["a","b","a","b","b","a"],
		 ["a","a","b","b","a","b"],
		 ["a","a","b","b","b","a"],
		 ["a","a","b","a","a","b"]
		]
    "ababaababaaabbabbaabbaabbaba", return true.
  */
  const vector<vector<char>> board = {
      {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
  const vector<vector<char>> board2 = {{'a', 'b'}, {'c', 'd'}};
  const vector<vector<char>> board3 = {
      {'b', 'a', 'a', 'b', 'a', 'b'}, {'a', 'b', 'a', 'a', 'a', 'a'},
      {'a', 'b', 'a', 'a', 'a', 'b'}, {'a', 'b', 'a', 'b', 'b', 'a'},
      {'a', 'a', 'b', 'b', 'a', 'b'}, {'a', 'a', 'b', 'b', 'b', 'a'},
      {'a', 'a', 'b', 'a', 'a', 'b'}};
  TestCaseStruct test_cases[] = {
      {{board, "ABCCED"}, true},
      {{board, "SEE"}, true},
      {{board, "ABCB"}, false},
      {{board2, "dbac"}, true},
      {{board3, "ababaababaaabbabbaabbaabbaba"}, true}};

  Solution solution;
  for (auto& test_case : test_cases) {
    if (solution.exist(test_case.input.board, test_case.input.word) ==
        test_case.expected_output) {
      cout << "test case = [" << test_case.input.word
           << "] is pass." << std::endl;
    } else {
      cout << "test case = [" << test_case.input.word
           << "] is fail." << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

## Result

Success
Details
Runtime: 100 ms, faster than 58.07% of C++ online submissions for Word Search.
Memory Usage: 19.3 MB, less than 53.49% of C++ online submissions for Word Search.

###### tags: `LeetCode-Medium` `C++`