LeetCode.79 单词搜索Java

╰半夏微凉° 2024-04-18 09:34 75阅读 0赞

# LeetCode.79 单词搜索 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
这是一个矩阵回溯算法典型题目，涉及到DFS和状态回溯重置

1.  偏移量数组在二维平面经常使用的
2.  对于这种搜索算法，代码编写也相对固定

package com.leetcode.solution;
    
    /** * @Author : fanc * @Date : 2019-09-03 17:55 * 单词搜索 */
    public class Solution79 { 
        /** * 定义变量 */
        private boolean[][] marked;
        private int[][] direction = { { -1, 0}, { 0, -1}, { 0, 1}, { 1, 0}};
        private int rows;
        private int cols;
        private char[][] board;
        private String word;
    
        /** * 判断是否在这个位置是否在矩阵里面 * @param i * @param j * @return */
        private boolean inArea(int i, int j) { 
            return i >= 0 && i < rows && j >= 0 && j < cols;
        }
    
        /** * 矩阵递归回溯深度搜索 * @param i * @param j * @param wordIndex * @return */
        private boolean matrixDfs(int i, int j, int wordIndex) { 
            if (board[i][j] == word.charAt(wordIndex) && !marked[i][j]) { 
                if (wordIndex == word.length() - 1) { 
                    return true;
                }
                marked[i][j] = true;
                for (int m = 0; m < direction.length; m++) { 
                    int newX = i + direction[m][0], newY = j + direction[m][1];
                    if (inArea(newX, newY) && matrixDfs(newX, newY, wordIndex + 1)) { 
                        return true;
                    }
                }
                marked[i][j] = false;
            }
            return false;
        }
    
        /** * 对每个矩阵每个点作为起点开始搜索 * @param board * @param word * @return */
        public boolean exist(char[][] board, String word) { 
            this.board = board;
            this.word = word;
            rows = board.length;
            if (rows == 0) { 
                return false;
            }
            cols = board[0].length;
            marked = new boolean[rows][cols];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cols; j++) { 
                    if (matrixDfs(i, j, 0)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
        public static void main(String[] args) { 
            char[][] board = { { 'a', 'a'}};
            String word = "aaa";
            Solution79 solution = new Solution79();
            boolean exist = solution.exist(board, word);
            System.out.println(exist);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/03a953238cfd46f39249f4fa1664eb25.png