# 79 Word Search

給一個char[][] board，和一個String word，在board中找word，如果找得到，return true，否則return false.

Concept:
use a boolean[][] visited to record which element in board has been visited.
for each element in board, search its neighbor to see if word can be found. If the searching process reach the end of word, return true.

Implementation:

1. 在Main時呼叫search()時，若可以找到word，return true。注意不能直接return search()，這樣只要一找不到就直接return false了，不會找其他element。
2. 在search()裡要注意return的條件。當index==word的長度時，return true，表示word裡所有字母都已經找到了。當x,y超過邊界、board[x][y]!=word.charAt(index)、此element已經被visit過，就要return false。
3. visited在呼叫search前要設成true，呼叫完之後要設回false

Pseudocode:
-main:

create a boolean[][] visited to record which element in board has been visited.
for each element in board,
    if element is same as word.charAt(0)
        call search()
    if search()==true, return true;
        return false

-search(index, board, index of word, word):

if index of word is word.length()
    return true;
if index of board is out of boundary,
    return false
visited[i][j]=true
if(any of current element's neighbor return true from calling search)
    return true;
visited[i][j]=false;
return false;

Code:

public class Solution {
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {

        int m = board.length;
        if(m==0)    return false;
        int n = board[0].length;
        visited = new boolean[m][n];

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]==word.charAt(0)){
                    boolean found = search(i,j,board,0,word);
                    if(found)   return found;
                }
            }
        }
        return false;
    }

    boolean search(int x, int y, char[][]board, int index, String word){
        if(index==word.length())
            return true;
        if(x < 0 || x > board.length-1 || y < 0 || y > board[x].length-1 || board[x][y]!=word.charAt(index) || visited[x][y])
            return false;
        visited[x][y]=true;
        if(search(x-1,y,board,index+1, word) || search(x,y-1,board,index+1, word) || search(x+1,y,board,index+1, word) ||search(x,y+1,board,index+1, word)){
            return true;
        }
        visited[x][y]=false;
        return false;
    }
}