剑指12 矩阵中的路径

  1. class Solution {
  2.     public boolean exist(char[][] board, String word) {
  3.         if (board == null || word == null)
  4.             return false;
  6.         int[][] visited = new int[board.length][board[0].length];
  7.         for (int i = 0; i < board.length; i++)
  8.             for (int j = 0; j < board[0].length; j++)
  9.                 visited[i][j] = 0;
  11.         int pathLength = 0;
  12.         for (int i = 0; i < board.length; i++)
  13.             for (int j = 0; j < board[0].length; j++)
  14.                 if (exitCore(board, word, i, j, visited, pathLength))
  15.                     return true;
  17.         return false;
  18.     }
  20.     private boolean exitCore(char[][] board, String word, int i, int j, int[][] visited, int pathLength) {
  21.         if (pathLength == word.length()) 
  22.             return true;
  24.         boolean exist = false;
  25.         if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == word.charAt(pathLength) && visited[i][j] == 0) {
  26.                 ++pathLength;
  27.                 visited[i][j] = 1;
  28.                 exist = exitCore(board, word, i + 1, j, visited, pathLength) || exitCore(board, word, i - 1, j, visited, pathLength) || exitCore(board, word, i, j - 1, visited, pathLength) || exitCore(board, word, i, j + 1, visited, pathLength);
  30.             if (!exist) {
  31.                 --pathLength;
  32.                 visited[i][j] = 0;
  33.             }
  34.     }
  36.     return exist;
  37.         }          
  38. }