现代码实现思路一深度优先搜索回溯以思路一为例进行调试部分代码解读

题目描述

单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。

同一个单元格内的字母不允许被重复使用。

输入输出样例

[[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],

word

[[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],

word

[[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],

word

在进行深度优先遍历的时候先判断表格中字母与word中第一个字母是否相同若相同则进行深度优先搜索每次搜索依次与word中的字母进行比较。

若每次比较字母相同则将此字母标记为已搜索继续进行搜索搜索到所有word中的字母则返回true。

若不相同则将此次搜索之前搜索过的字母标记为未搜索。

并从开始搜索的第一个字母的下一个字母进行判断搜索直至搜索完整个图。

2、复杂度分析

个点。

搜索失败最深的搜索的深度为(L-1)每个点有上下左右四个搜索方向方式搜索过的点不进行搜索所以为

O(MN3L

函数进行深度优先搜索尝试在board上找到单词wordvoid

board,

用来标记当前位置是否已经访问过避免重复访问vectorvectorbool

mark(board.size(),

vectorbool(board[0].size()));bool

flag

函数进行深度优先搜索尝试在board上找到单词wordvoid

board,

用来标记当前位置是否已经访问过避免重复访问vectorvectorbool

mark(board.size(),

vectorbool(board[0].size()));bool

flag

{{A,B,C,E},{S,F,C,S},{A,D,E,E}};//

wordstring

(s.exist(board,word)){couttrue;}else{coutfalse;}return

}部分代码解读

vectorbool(board[0].size()));作用是创建一个与

board