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

• 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;
}
};``````

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