79. Word search (medium string array matrix backtracking)

79. Word search

Given a m x n Two dimensional character grid board And a string word word . If word Exists in the grid , return true ; otherwise , return false .

The words must be in alphabetical order , It's made up of letters in adjacent cells , among “ adjacent ” Cells are those adjacent horizontally or vertically . Letters in the same cell are not allowed to be reused .

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

Tips ：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word It consists of upper and lower case English letters only

Advanced ： You can use search pruning techniques to optimize solutions , Make it board Larger situations can solve problems faster ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/word-search
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

backtracking . Need to consider marking letters , And trace back to delete the tag after use , In addition, you need to pay attention to how to get the return value .

Answer key （Java）

class Solution {
    
    public boolean exist(char[][] board, String word) {
    
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                boolean flag = check(board, word, i, j, 0);
                if (flag) {
    
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(char[][] board, String word, int i, int j, int k) {
    
        if (board[i][j] != word.charAt(k)) {
    
            return false;
        } else if (k == word.length() - 1) {
    
            return true;
        }
        char ch = board[i][j];
        board[i][j] = '0';// Mark directly on the original array 
        int[][] dirs = {
    {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0}};// Auxiliary array moving up, down, left and right 
        boolean result = false;
        for (int[] dir : dirs) {
    
            int row = i + dir[0], col = j + dir[1];
            if (row >= 0 && row < board.length && col >= 0 && col < board[0].length) {
    
                if (board[row][col] != '0') {
    
                    boolean flag = check(board, word, row, col, k + 1);
                    if (flag) {
    // flag  by  true  Indicates that the end of the string has been reached 
                        result = true;
                        break;
                    }
                }
            }
        }
        board[i][j] = ch;// Restore array 
        return result;
    }
}