Simple C++ using DFS with O(1) space

• Just implemented a simple C++ using DFS with O(1) space. Assuming that word does not contain '\$'
'''
class Solution {
bool dfs(vector<vector<char>>&board, int i, int j, string word, int index){
if(index == word.length()) return true;
int m = board.size(), n = board[0].size();
if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '\$' || board[i][j] != word[index]) return false;
char c = board[i][j];
board[i][j]='\$';
vector<pair<int, int>> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
bool ret = false;
for(auto p: dir)
if(dfs(board, i + p.first, j + p.second, word, index+1)) {ret = true;break;}
board[i][j] = c;
return ret;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.size() == 0 || board[0].size() == 0 || word.length() == 0) return false;
for(int i = 0; i < board.size(); ++i){
for(int j = 0; j < board[0].size(); ++j){
if(board[i][j] == word[0])
if(dfs(board, i, j, word, 0)) return true;
}
}
return false;
}
};
'''

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