[leetcode] Word Search

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

public class Solution { public boolean exist(char[][] board, String word) { boolean visited[][] = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++){ for (int j = 0; j < board[i].length; j++){ if (dfs(board, word, 0, i, j, visited)) return true; } } return false; } public boolean dfs(char[][] board, String word, int wordIndex, int i, int j, boolean[][] visited){ if (i < 0 || i > board.length-1 || j < 0 || j > board[i].length-1 || wordIndex >= word.length()) return false; if (visited[i][j] || board[i][j] != word.charAt(wordIndex)) return false; if (wordIndex == word.length()-1 && !visited[i][j] && board[i][j] == word.charAt(wordIndex)) return true; boolean result = false; visited[i][j] = true; if (dfs(board, word, wordIndex+1, i-1, j, visited)|| dfs(board, word, wordIndex+1, i+1, j, visited)|| dfs(board, word, wordIndex+1, i, j-1, visited)|| dfs(board, word, wordIndex+1, i, j+1, visited)){ result = true; } visited[i][j] = false; return result; } }