Accepted very short Java solution. No additional space.


  • 210
    P

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

  • 3
    D

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

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


  • 20
    P

    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.


  • 6
    S

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


  • 2
    G

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


  • 1
    Q

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


  • 5
    J

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


  • 0
    Q

    Thanks a lot!


  • 77
    H
    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.


  • 7
    S

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


  • 0
    R

    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?


  • 0

    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.


  • 9

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

  • 2
    A

    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


  • 0
    H

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


  • 2
    P

    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.


  • 0
    P

    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)).


  • 0
    D

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


  • 0
    W

    I tried your code and it didn't detect loop.
    ABCE
    SFCS
    ADEE
    if I use word BCCFB, the output is true, but online judge for this case if false.


  • 5
    T

    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.


Log in to reply
 

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