Find Words in a 2D Board using Java


  • 0
    P

    ...
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;

    public class WordSearch {

    public static void main(String[] args) {
    			
    	char[][] newBoard = {
    	                     {'o','a','a','n'},
    						 {'e','t','a','e'},
    						 {'i','h','k','r'},
    						 {'i','f','l','v'}
    						};
    	String[] words = {"oath","pea","eat","rain"};
    	
    	Arrays.stream(findWords(newBoard, words).toArray())
          .forEach(System.out::println);
    
    }
    	
    public static List<String> findWords(char[][] board, String[] words) {
    	List<String> matches = new ArrayList<String>();
    	for(String word : words) {
    	    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)) matches.add(word);
    	    	}
    	    }
    	}
        return matches;
    }
    
    private static 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;
    }
    

    }
    ...


Log in to reply
 

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