Another recursive solution (JAVA)


  • 0
    Q
    public class Solution {
        public boolean exist(char[][] board, String word) {
    		LinkedList<Character> charList = new LinkedList<Character>();
    		for (char c:word.toCharArray()){
    			charList.add(c);
    		}
    		for (int i=0;i<board.length;i++){
    			for (int j=0;j<board[0].length;j++){
    				if (find(board, charList, i, j)){
    					return true;
    				}
    			}
    		}
    		return false;
        }
    
    	private boolean find(char[][] board, Deque<Character> word, int i, int j){
    		if (word.isEmpty()){
    			return true;
    		}
    		if (i <0 || i>board.length-1 || j<0 || j>board[0].length-1){
    			return false;
    		}
    		Character c = word.peek();
    		if (board[i][j] == c){
    		    word.poll();
    			board[i][j]= 0;
    			if(find(board, word, i-1, j)||find(board, word, i+1, j)||
    			                find(board, word, i, j-1)||find(board, word, i, j+1)){
    			    return true;                    
    			}
    			board[i][j] = c;
    			word.push(c);
    		}
    		return false;
    	}
    }

Log in to reply
 

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