Word Search (LeetCode Array)

Question: Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea: Depth-first search with backtracking. For each block, start to match the string one character by one character. Whenever a character board[i][j] is matched, mark it as board[i][j]='#' (representing it has been used) then go forward to board[i+1][j], board[i-1][j], board[i][j+1] and board[i][j-1]. If board[i][j] is out of boundary or board[next] does not match with string[next], return false. When all the characters of the string is matched, return true. When we roll back to the point board[i][j], do not forget to set it back to the original character, otherwise when we initial another search from the next point, e.g. board[i][j-1], the path can not go left, since it is '#'.

Time: O(n^4) Space: O(n^2)

Code:

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