1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Word Search
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/word-search/
7+ Notes:
8+ Given a 2D board and a word, find if the word exists in the grid.
9+ The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are
10+ those horizontally or vertically neighboring. The same letter cell may not be used more than once.
11+ For example,
12+ Given board =
13+ [
14+ ["ABCE"],
15+ ["SFCS"],
16+ ["ADEE"]
17+ ]
18+ word = "ABCCED", -> returns true,
19+ word = "SEE", -> returns true,
20+ word = "ABCB", -> returns false.
21+
22+ Solution: DFS.
23+ */
24+ public class Solution {
25+ public boolean exist (char [][]board ,String word ) {
26+ int m =board .length ;
27+ if (m ==0 )return false ;
28+ int n =board [0 ].length ;
29+ if (n ==0 )return false ;
30+ if (word .length () ==0 )return true ;
31+ boolean [][]visited =new boolean [m ][n ];
32+ for (int i =0 ;i <m ; ++i ) {
33+ for (int j =0 ;j <n ; ++j ) {
34+ if (board [i ][j ] ==word .charAt (0 ) &&existRe (board ,i ,j ,word ,0 ,visited )) {
35+ return true ;
36+ }
37+ }
38+ }
39+ return false ;
40+ }
41+ public boolean existRe (char [][]board ,int i ,int j ,String word ,int cur ,boolean [][]visited ) {
42+ if (cur ==word .length ())return true ;
43+ int m =board .length ;
44+ int n =board [0 ].length ;
45+ if (i <0 ||i >=m ||j <0 ||j >=n )return false ;
46+ if (visited [i ][j ] ==true || (board [i ][j ] !=word .charAt (cur )))return false ;
47+ visited [i ][j ] =true ;
48+ if (existRe (board ,i +1 ,j ,word ,cur +1 ,visited ))return true ;
49+ if (existRe (board ,i -1 ,j ,word ,cur +1 ,visited ))return true ;
50+ if (existRe (board ,i ,j +1 ,word ,cur +1 ,visited ))return true ;
51+ if (existRe (board ,i ,j -1 ,word ,cur +1 ,visited ))return true ;
52+ visited [i ][j ] =false ;
53+ return false ;
54+ }
55+ }
