# Accepted very short Java solution. No additional space.

• Here accepted solution based on recursion. To save memory I decuded to apply bit mask for every visited cell. Please check board[y][x] ^= 256;

``````public boolean exist(char[][] board, String word) {
char[] w = word.toCharArray();
for (int y=0; y<board.length; y++) {
for (int x=0; x<board[y].length; x++) {
if (exist(board, y, x, w, 0)) return true;
}
}
return false;
}

private boolean exist(char[][] board, int y, int x, char[] word, int i) {
if (i == word.length) return true;
if (y<0 || x<0 || y == board.length || x == board[y].length) return false;
if (board[y][x] != word[i]) return false;
board[y][x] ^= 256;
boolean exist = exist(board, y, x+1, word, i+1)
|| exist(board, y, x-1, word, i+1)
|| exist(board, y+1, x, word, i+1)
|| exist(board, y-1, x, word, i+1);
board[y][x] ^= 256;
return exist;
}``````

• nice solution, why you use 'board[y][x] ^= 256;' ? not board[y][x] ^= 64;

I think you can use any like 2^n, right?

• No.
board[y][x] ^= 256 it's a marker that the letter at position x,y is a part of word we search.
After board[y][x] ^= 256 the char became not a valid letter. After second board[y][x] ^= 256
it became a valid letter again.

• beautiful code!!! Amazing! Your understanding of char type is far beyond me.

• I think this only works for non-Unicode. However, for Java, char data type is a single 16-bit Unicode character.

• Do you know the time and space complexity of your code?

• It is O(4^n) since we are recursively traversing the 4 adjacent cells at each step.

• Thanks a lot!

• ``````public class Solution {
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++)
for(int j = 0; j < board[0].length; j++){
if(exist(board, i, j, word, 0))
return true;
}
return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
if(ind == word.length()) return true;
if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
return false;
board[i][j]='*';
boolean result =    exist(board, i-1, j, word, ind+1) ||
exist(board, i, j-1, word, ind+1) ||
exist(board, i, j+1, word, ind+1) ||
exist(board, i+1, j, word, ind+1);
board[i][j] = word.charAt(ind);
return result;
}
``````

}

My java code use similar idea.
restriction is '*' cannot be present in the input char matrix.

• Your code works, but when your algorithm is running, board[][] is changed, which prevents it from concurrent usage.

• no I doubted, we have O(mn) for each for loop, then we search the whole elements again, which is O(mn) in total it is O(m^2n^2) time complexity, but no idea about space complexity, can anyone please tell me how do you do that for recursion?

• Hi, rabeeh. I think the space complexity is `O(4mn)` if the function call stack is taken into account. In each cell, we recursively call its `4` four neighbors and there are `mn` cells in total.

• I have a similar code in C++, in which I use `char*` instead of `string` to speed up the code.

``````class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (search(board, i, j, word.c_str()))
return true;
return false;
}
private:
bool search(vector<vector<char>>& board, int r, int c, const char* word) {
if (!word[0]) return true;
int m = board.size(), n = board[0].size();
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[0]) return false;
board[r][c] = '\$';
if (search(board, r - 1 ,c, word + 1) || search(board, r + 1, c, word + 1) ||
search(board, r, c - 1, word + 1) || search(board, r, c + 1, word + 1))
return true;
board[r][c] = word[0];
return false;
}
};``````

• First, you should keep board and word static, instead of passing by at each recursion, that will save a lot space.
Second, your code cant not detect loop. You either need a static variable 'stack' to get in and pop out every time, or you need to add a 'Path' variable at your exist() function, to record the path and check if it has been visited already

• I don't understand board[y][x] ^= 256. Can I leave the two "board[y][x] ^= 256" out?

• Hi jianchao.li.fighter. I think the space complexity is O(mn). There is only one call stack at any given time. And the max length is mn. 4 calls will not happen at the same time.

• Hi rabeeh. I think the time complexity is exponential. There are mn loops. But with the back tracking, each point can be visited many times. The total complexity is about O(mn*3^(nm)).

• board[i][j] = word.charAt(ind);
What does this line do?

• I tried your code and it didn't detect loop.
ABCE
SFCS
• Re `^256` questions: those two could be also `board[y][x] = 0` before and `board[y][x] = word[i]` after the recursive calls. Then there's no question if it's unicode or not.