/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/varexist=function(board, word){vardfs=function(board, word, vis, x, y, index){if(index == word.length){returntrue;}for(let d =0; d <4; d++){let x_ = x + dirt[d][0];let y_ = y + dirt[d][1];if(x_ >=0&& x_ < m && y_ >=0&& y_ < n && vis[x_][y_]==0&& word[index]== board[x_][y_]){
vis[x_][y_]=1;if(dfs(board, word, vis, x_, y_, index +1)){returntrue;}
vis[x_][y_]=0;}}returnfalse;};let m = board.length;let n = board[0].length;let vis =Array(m).fill(null).map(()=>Array(n).fill(0));let dirt =[[1,0],[0,1],[-1,0],[0,-1]];for(let i =0; i < m; i++){for(let j =0; j < n; j++){if(word[0]== board[i][j]){
vis[i][j]=1;if(dfs(board, word, vis, i, j,1)){returntrue;}
vis[i][j]=0;}}}returnfalse;};
69 分割回文串
回溯
startIndex:从0开始,表示切割线。
判断当前切割的子串( [ startIndex, i ] )是否是回文字符串:双指针法,一前一后两个指针向中间移动。
递归终止条件:切割线到str最后了。
下一次递归的切割点:当前遍历字母的索引i + 1。
varisValid=function(str){let start =0;let end = str.length -1;while(start < end){if(str.charAt(start)!= str.charAt(end)){returnfalse;}
start++;
end--;}returntrue;};/**
* @param {string} s
* @return {string[][]}
*/varpartition=function(s){vartraversal=function(s, startIndex){if(startIndex == s.length){
res.push(path.slice());return;}for(let i = startIndex; i < s.length; i++){let tmp = s.slice(startIndex, i +1);if(isValid(tmp)){
path.push(tmp);traversal(s, i +1);
path.pop();}}}let res =[];let path =[];traversal(s,0);return res;};
70 N皇后
回溯
row:遍历的行数,i:遍历的列数。
递归结束条件:最后一行放置完Q了,注意收集数组时应该转为字符串形式。
varisValid=function(chessboard, row, col, n){for(let i =0; i < row; i++){for(let j =0; j < n; j++){if(chessboard[i][j]=='Q'&&(j == col || Math.abs(i - row)== Math.abs(j - col))){returnfalse;}}}returntrue;}/**
* @param {number} n
* @return {string[][]}
*/varsolveNQueens=function(n){vartraversal=function(chessboard, row, n){if(row == n){let tmp = chessboard.slice()for(let i =0; i < n; i++){
tmp[i]= tmp[i].join('');}
res.push(tmp);return;}for(let i =0; i < n; i++){if(isValid(chessboard, row, i, n)){
chessboard[row][i]='Q';traversal(chessboard, row +1, n);
chessboard[row][i]='.';}}};let res =[];let chessboard =Array(n).fill(null).map(()=>Array(n).fill('.'));traversal(chessboard,0, n);return res;};