小言_互联网的博客

leetcode79. 单词搜索 网格地图搜索+回溯经典写法啦

448人阅读  评论(0)

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

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

示例:

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

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

思路:搜索回溯基本上是经典模板题了。


  
  1. class Solution {
  2. private boolean[][] marked;
  3. // x-1,y
  4. // x,y-1 x,y x,y+1
  5. // x+1,y
  6. private int[][] direction = {{- 1, 0}, { 0, - 1}, { 0, 1}, { 1, 0}};
  7. // 盘面上有多少行
  8. private int m;
  9. // 盘面上有多少列
  10. private int n;
  11. private String word;
  12. private char[][] board;
  13. public boolean exist(char[][] board, String word) {
  14. m = board.length;
  15. if (m == 0) return false;
  16. n = board[ 0].length;
  17. marked = new boolean[m][n];
  18. this.word = word;
  19. this.board = board;
  20. for ( int i = 0; i < m; i++)
  21. for ( int j = 0; j < n; j++)
  22. if (dfs(i, j, 0))
  23. return true;
  24. return false;
  25. }
  26. private boolean dfs(int i, int j, int start) {
  27. if (start == word.length() - 1) {
  28. return board[i][j] == word.charAt(start);
  29. }
  30. if (board[i][j] == word.charAt(start)) {
  31. marked[i][j] = true;
  32. for ( int k = 0; k < 4; k++) {
  33. int newX = i + direction[k][ 0];
  34. int newY = j + direction[k][ 1];
  35. if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {
  36. if (dfs(newX, newY, start + 1)) {
  37. return true;
  38. }
  39. }
  40. }
  41. marked[i][j] = false;
  42. }
  43. return false;
  44. }
  45. }

 


转载:https://blog.csdn.net/hebtu666/article/details/104429737
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场