LC79—单词搜索

LC79---单词搜索
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

79. 单词搜索

难度中等820

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

DFS

class Solution {
   
   private static final int[][] DIR = {
   {
   -1, 0}, {
   0, -1}, {
   0, 1}, {
   1, 0}};
    private int rows;
    private int cols;
    private int len;
    private boolean[][] visied;
    private char[] charArray;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
   
        rows = board.length;
        cols = board[0].length;
        if (rows == 0) {
   
            return false;
        }

        visied = new boolean[rows][cols];
        this.len = word.length();
        this.charArray = word.toCharArray();
        this.board = board;
        for (int i = 0; i < rows; i++) {
   
            for (int j = 0; j < cols; j++) {
   
                if (dfs(i, j, 0)) {
   
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int begin) {
   
        if (begin == len - 1) {
   
            return board[x][y] == charArray[begin];
        }
        if (board[x][y] == charArray[begin]) {
   
            visied[x][y] = true;
            for (int i = 0; i < DIR.length; i++) {
   
                int newx = x + DIR[i][0];
                int newy = y + DIR[i][1];
                if (inArea(newx, newy) && !visied[newx][newy]) {
   
                    if (dfs(newx, newy, begin + 1)) {
   
                        return true;
                    }
                }

            }
            visied[x][y] = false;
        }
        return false;
    }

    private boolean inArea(int x, int y) {
   
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}
本文来源面相薪水编程,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8170

发表评论