知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 93 - 单词搜索 ## 题目(LeetCode 79) 给定 m×n 网格和单词,判断单词是否存在于网格中(相邻单元格字母连接)。 ## 解法:回溯 ```java class Solution { public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (dfs(board, word, i, j, 0)) return true; } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int k) { if (k == word.length()) return true; if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false; if (board[i][j] != word.charAt(k)) return false; char tmp = board[i][j]; board[i][j] = '#'; boolean found = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1); board[i][j] = tmp; return found; } } ``` ## 复杂度 - 时间 O(m·n·3^L),L 为单词长度 - 空间 O(L) ## 一句话总结 从每个格子出发 DFS,用原地标记避免重复访问,回溯时恢复。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入