PattySung

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

->題目會給一個word單字，我們要找在這個board中，是否可以找到這個字詞。有點類似Leetcode-200. Number of Islands的題目

<解題> 方式一

可以先用迴圈來跑，看第一個char是否有在這個board當中，如果有的話，我們來搜尋這個char的前後左右有沒有符合接下來的字詞，所以我們建立一個search方法
由於被訪問過的字在同一次搜尋中，不能被再度訪問，所以我們在前面要設置一個boolean visited方法，如果被訪問到時，要設置為true。
搜尋其上下左右（index+1)，如果都符合接下來的字詞，return true，都沒有的話return false
if(index == word.length())，代表已經成功找到完整的單詞匹配，所以return true


public class Solution {
    static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        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((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean search(char[][]board, String word, int i, int j, int index){
        if(index == word.length()){
            return true;
        }
        
        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }
        
        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) || 
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) || 
           search(board, word, i, j+1, index+1)){
            return true;
        }
        
        visited[i][j] = false;
        return false;
    }
}

Time: O((rows * columns)^2) Space: O((rows * columns))

DFS


public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }

        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }

        visited[i][j] = true;

        if (dfs(board, word, i - 1, j, index + 1, visited) ||
            dfs(board, word, i + 1, j, index + 1, visited) ||
            dfs(board, word, i, j - 1, index + 1, visited) ||
            dfs(board, word, i, j + 1, index + 1, visited)) {
            return true;
        }

        visited[i][j] = false;
        return false;
    }
}

Leetcode-79. Word Search

<解題> 方式一

DFS