- 79. Word Search
- Difficulty: Medium
- Given a 2D board and a Word, find if the Word exists in the grid.
- The Word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
- For example,
- Given board =
- [
- ['A','B','C','E'],
- ['S','F','C','S'],
- ['A','D','E','E']
- ]
- Word = "ABCCED", -> returns true,
- Word = "SEE", -> returns true,
- Word = "ABCB", -> returns false.
- Solution
- class Solution {
- ? ?private boolean isMatch = false;
- ? ?private boolean[][] visited;
- ? ?public boolean exist(char[][] board, String Word) {
- ? ? ? ?if (board.length == 0 || board[0].length == 0) {
- ? ? ? ? ? ?return false;
- ? ? ? }
- ? ? ? ?visited = new boolean[board.length][board[0].length];
- ? ? ? ?for (int i = 0; i <board.length; i++) {
- ? ? ? ? ? ?for (int j = 0; j < board[0].length; j++) {
- ? ? ? ? ? ? ? ?dfs(Word,0,board,i,j);
- ?
- ? ? ? ? ? }
- ? ? ? }
- ? ? ? ?
- ? ? ? ?return isMatch;
- ? }
- ? ?
- ? ?private boolean isValid(int i, int j, char[][] board) {
- ? ? ? ?//3
- ? ? ? int height = board.length;
大专栏 leetcode 79. Word Search> ? ? ? ?//4
- ? ? ? ?int width = board[0].length;
- ? ? ?
- ? ? ? ?if (i> height - 1 || ?j> width - 1 || i <0 || j < 0){
- ? ? ? ? ? ?return false;
- ? ? ? }
- ? ? ? ?if(visited[i][j] == true) {
- ? ? ? ? ? ?return false;
- ? ? ? }
- ? ? ? ?return true;
- ? ? ? ?
- ? }
- ? ?
- ? ?private void dfs (String Word, int idx, char[][]board, int i, int j) {
- ? ? ? ?if (!isValid(i,j,board)) {
- ? ? ? ? ? ?return;
- ? ? ? }
- ? ? ? ?if (isMatch) {
- ? ? ? ? ? ?return;
- ? ? ? }
- ?
- ? ? ? ?if (idx>= Word.length()) {
- ? ? ? ? ? ?return;
- ? ? ? }
- ? ? ? ?if(idx == Word.length() - 1 && Word.charAt(idx) == board[i][j]) {
- ? ? ? ? ? ?isMatch = true;
- ? ? ? ? ? ?//ystem.out.println("MMMAtch:now word:" + Word.substring(0,idx + 1));
- ? ? ? ?//stem.out.println("MMMAtch:"+ idx + "i :" + i + "j:" + j);
- ? ? ? ? ? ?for (int k = 0; k < visited.length; k++) {
- ? ? ? ? ? ? ? ?for (int h = 0; h < visited[0].length; h++) {
- ? ? ? ? ? ? ? ? ? // System.out.print(visited[k][h]);
- ? ? ? ? ? ? ? }
- ? ? ? ? ? ? ? ?//stem.out.println(" ");
- ? ? ? ? ? }
- ? ? ? ? ? ?return;
- ? ? ? }
- ? ? ? ?//stem.out.println("now word:" + Word.substring(0,idx + 1));
- ? ? ? ?//stem.out.println(idx + "i :" + i + "j:" + j);
- ? ? ? ?if(Word.charAt(idx) == board[i][j]) {
- ? ? ? ? ? ? ?visited[i][j] = true;
- ? ? ? ? ? ? ?dfs(Word,idx + 1,board,i + 1,j);
- ? ? ? ? ? ? ?dfs(Word,idx + 1,board,i,j + 1);
- ? ? ? ? ? ? ?dfs(Word,idx + 1,board,i - 1,j);
- ? ? ? ? ? ? ?dfs(Word,idx + 1,board,i,j - 1);
- ? ? ? ? ? ? ?visited[i][j] = false;
- ? ? ? }
- ? ? ? ?return;
- ? }
- }
思路: dfs 即可.
DFS 使用栈, 思路是对于图到的所有顶点 u, 如果 u 未被访问, 则访问 u 所在的联通块.
访问顶点 u: 设置 u 被访问, 枚举从 u 出发可以到达的所有顶点 v, 如果 v 未被访问, 则递归访问 v
- DFS(u) {
- vis[u] = true;
- for (从 u 出发能到达的 v) {
- if vis[v] == false
- {
- DFS(v)
- }
- }
- }
有时也可以不显式地定义一个 visitted 数组, 可以直接更改图, 访问过的改为 0(如 leetcode695), 也可以有比较灵活的改动, 比如递归调用的 DFS 可以有返回值之类的.
还有一个小技巧要注意的是可以在递归调用的函数里判断是否这次调用时是否是 valid 的, 而不是在调用这个函数时判断, 这样就可以不管三七二十一调用这个函数就可以了, 因为调用不 valid 也没有问题直接返回就可以了.
回到这道题的话, 最好在 main 方法里只调用一次 dfs, 其他的东西都扔到 dfs 本身去做. 尽量能够简化写就简化写, 可以帮助减少思维负担.
除此之外, 如果说需要像这道题一样保证每次只出现一次, 就可以把 visited 在其所有的后续节点都遍历完了之后重新设为 false.
来源: http://www.bubuko.com/infodetail-3350419.html