网站建设哪便宜,vps试用30天,网站建设和制作怎么赚钱,企业网站作用单词搜索 题解1 回溯#xff08;需要改变起点#xff09; 给定一个
m x n 二维字符网格
board 和一个字符串单词
word 。如果
word 存在于网格中#xff0c;返回
true #xff1b;否则#xff0c;返回
false 。 单词必须按照字母顺序#xff0c;通过相邻的单元格内… 单词搜索 题解1 回溯需要改变起点 给定一个
m x n 二维字符网格
board 和一个字符串单词
word 。如果
word 存在于网格中返回
true 否则返回
false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题解1 回溯需要改变起点
class Solution {bool res false;int ls, cs;
public:void backtrace(vectorvectorchar board, string word, int r, int c, int p){// 顺序很重要, 养成习惯先判断return条件再排除其他if(p word.size()){res true;return;}// 边界if(r ls || c cs || r 0 || c 0 || res) return;// 有一个错误字符直接return换下一种组合/该字符起点不对需要换if(board[r][c] ! word[p]) return;// 相当于 used/visited——// 此题条件下往左往上往下往右可能会重复选很多格子但是当前格子不允许重复选board[r][c] (char)(-board[r][c]);// 水平 左右backtrace(board, word, r, c1, p1);backtrace(board, word, r, c-1, p1);// 垂直 (上下)backtrace(board, word, r1, c, p1);backtrace(board, word, r-1, c, p1);// 撤回操作走不通需要换起点// backtrace结束后会到下一个出发点若(r, c)是中途格子需要复位board[r][c] (char)(-board[r][c]);}bool exist(vectorvectorchar board, string word) {ls board.size();cs board[0].size();// 遍历搜索起点for(int i 0; i ls; i){for(int j 0; j cs; j){// 搜索起点改变if(board[i][j] word[0])backtrace(board, word, i, j, 0);if(res) return true;}}return res;}
};
