Share my 9ms solution


  • 0
    S
    public boolean exist(char[][] board, String word) {
         int h = board.length;
         int w = board[0].length;
         boolean[][] mark = new boolean[h][w];
         int[][] axis = {{0,1,0,-1},{1,0,-1,0}};
         for (int i = 0; i < h; i++) 
              for (int j = 0; j < w; j++)
                   if (helper(board, word, mark, 0, i, j, h, w, axis)) 
                        return true;
         return false;
    }
    	
    private boolean helper(char[][] board, String word, boolean[][] mark, int id, int i, int j, int h, int w, int[][] axis) {
         if (board[i][j] != word.charAt(id)) return false;
         if (id == word.length()-1) return true;
         boolean res = false;
         mark[i][j] = true;
         for (int k = 0; k < 4; k++) {
              int x = i + axis[0][k];
              int y = j + axis[1][k];
              if (x>=0 && x<h && y>=0 && y<w && !mark[x][y])
                   res = res||helper(board, word, mark, id+1, x, y, h, w, axis);
         }
         mark[i][j] = false;
         return res;
    }
    

Log in to reply
 

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