广州seo网站多少钱,数据分析师,茂名专业做网站,wordpress 主题生成给定一个二维网格和一个单词#xff0c;找出该单词是否存在于网格中。
单词必须按照字母顺序#xff0c;通过相邻的单元格内的字母构成#xff0c;其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board [ [A,B,C…给定一个二维网格和一个单词找出该单词是否存在于网格中。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ]
给定 word ABCCED, 返回 true. 给定 word SEE, 返回 true. 给定 word ABCB, 返回 false.
思路搜索回溯基本上是经典模板题了。
class Solution {private boolean[][] marked;// x-1,y// x,y-1 x,y x,y1// x1,yprivate int[][] direction {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};// 盘面上有多少行private int m;// 盘面上有多少列private int n;private String word;private char[][] board;public boolean exist(char[][] board, String word) {m board.length;if (m 0)return false;n board[0].length;marked new boolean[m][n];this.word word;this.board board;for (int i 0; i m; i)for (int j 0; j n; j)if (dfs(i, j, 0))return true;return false;}private boolean dfs(int i, int j, int start) {if (start word.length() - 1) {return board[i][j] word.charAt(start);}if (board[i][j] word.charAt(start)) {marked[i][j] true;for (int k 0; k 4; k) {int newX i direction[k][0];int newY j direction[k][1];if (newX 0 newX m newY 0 newY n !marked[newX][newY]) {if (dfs(newX, newY, start 1)) {return true;}}}marked[i][j] false;}return false;}
}
