👂 ▶ 幸福就是 (163.com)
👂 ▶ 当爱在靠近 (163.com)
目录
🚩括号生成
AC DFS
🌼单词搜索
AC DFS
🎂分割回文串
AC DFS+DP
AC DFS+记忆化
🌼N 皇后
AC DFS
🚩括号生成
22. 括号生成 - 力扣（LeetCode）
AC DFS
class Solution {
private:
string temp; // 临时答案
vector<string> ans;
void dfs(int n, int l, int r) { // 左括号数 l, 右括号数 r
// 递归出口
if (temp.size() == 2*n) {
ans.push_back(temp);
return;
}
// 递归
if (l < n) {
temp.push_back('(');
dfs(n, l + 1, r);
temp.pop_back(); // 回溯时取消标记
}
if (r < l) { // 为了保证匹配，这里 r < l，保证左边的 '(' 匹配 右边的 ')'
temp.push_back(')');
dfs(n, l, r + 1);
temp.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0);
return ans;
}
};🌼单词搜索
79. 单词搜索 - 力扣（LeetCode）
AC DFS
每个点 DFS 一次，有任一路径满足即可
class Solution {
private:
int nex[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; // 4 个方向
int vis[8][8];
// (x, y) 开始, word 中第 count 个字符
bool dfs(int x, int y, int count, vector<vector<char>>& board, string word) {
int num = word.size(), m = board.size(), n = board[0].size();
// 递归出口
if (board[x][y] != word[count])
return false;
if (count == num - 1)
return true;
vis[x][y] = 1; // 标记
int result = 0;
// 递归
for (int i = 0; i < 4; ++i) {
int xx = x + nex[i][0], yy = y + nex[i][1];
if (xx >= 0 && xx < m && yy >= 0 && yy < n && !vis[xx][yy]) { // 未越界 && 未访问
int flag = dfs(xx, yy, count + 1, board, word); // 递归
if (flag) {
result = 1;
break;
}
}
}
vis[x][y] = 0; // 取消标记
return result;
}
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
// 从每一个点开始 DFS
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int flag = dfs(i, j, 0, board, word);
if (flag)
return true;
}
return false;
}
};🎂分割回文串
131. 分割回文串 - 力扣（LeetCode）
AC DFS+DP
1）常规判断回文，用双指针 O(n)，这里采用 DP O(1)👇
a. 含义：dp[i][j] == 1，字符串片段 [i, j] 是回文串
b. 递推式：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
c. 初始化：全部初始化为 1，两层 for 循环中，加个 s[i] == s[j] 的条件即可
d. 遍历顺序：根据递推式，且考虑到 i <= j，i 由 i + 1 得到，i 从 i = n - 1 开始遍历，j 从 i 开始
2）注意递归 dfs(s, j + 1)，而不是 dfs(s, x + 1)，因为当前 [x, j] 部分已经分割出来，并插入 temp 了，下一部分应该从 j + 1 开始
3）坑：第 33 行，dp 递推那里，j = i + 1 开始，否则当 i = 0, j = i = 0，此时 j - 1 == -1，会出现 dp[1][-1] 导致溢出
时间 O(n * 2^n)
O(n) 字符串长度
O(2^n) 长度为 n 的字符串划分方案数 2^(n-1) ≈ O(2^n)
class Solution {
private:
vector<string> temp; // 临时答案
vector<vector<string>> ans;
vector<vector<int>> dp;
int n; // 字符串 s 长度
// 分割字串 [x, ...]
void dfs(string s, int x) {
// 递归出口：字符串末尾, 分割完毕
if (x == n) {
ans.push_back(temp);
return;
}
// [x, x] ... [x, n-1]
for (int j = x; j < n; ++j) {
if (dp[x][j]) { // 回文
temp.push_back(s.substr(x, j - x + 1));
// [x, j] -> [j + 1, ...]
// 递归分割下一部分
dfs(s, j + 1);
temp.pop_back(); // 回溯 恢复现场
}
}
}
public:
vector<vector<string>> partition(string s) {
n = s.size();
// 初始化 dp 为 1
dp.resize(n, vector<int>(n, 1)); // 等价于 assign
// dp 递归式
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j) // j = i + 1 开始，防止 i = 0 时 溢出
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
dfs(s, 0); // 下标 0 开始分割 [0, ...]
return ans;
}
};AC DFS+记忆化
将上面 O(1) 的 dp 变成 DFS 中的记忆化，本质一样，都是通过记录已有的结果，减少重复计算
记忆化一般用递归 return 实现
比 DP O(1) 求回文，慢很多
class Solution {
private:
vector<string> temp; // 临时答案
vector<vector<string>> ans;
vector<vector<int>> dp;
int n; // 字符串 s 长度
// 分割字串 [x, ...]
void dfs(string s, int x) {
// 递归出口：字符串末尾, 分割完毕
if (x == n) {
ans.push_back(temp);
return;
}
// [x, x] ... [x, n-1]
for (int j = x; j < n; ++j) {
if (isParlin(x, j, s) == 1) { // 回文
temp.push_back(s.substr(x, j - x + 1));
// [x, j] -> [j + 1, ...]
// 递归分割下一部分
dfs(s, j + 1);
temp.pop_back(); // 回溯 恢复现场
}
}
}
// 记忆化搜索判断回文
// 0 未搜索 1 回文 -1 非回文
int isParlin(int l, int r, string s) {
if (dp[l][r])
return dp[l][r]; // 返回已有结果
if (l >= r)
return dp[l][r] = 1; // 一个元素--回文
return dp[l][r] = (s[l] == s[r]) ? isParlin(l+1, r-1, s) : -1;
}
public:
vector<vector<string>> partition(string s) {
n = s.size();
dp.resize(n, vector<int>(n)); // 初始化为 0
dfs(s, 0); // 下标 0 开始分割 [0, ...]
return ans;
}
};🌼N 皇后
51. N 皇后 - 力扣（LeetCode）
AC DFS
col[] 标记列，dfs(int r) 参数 r 标记行
两个点，行差值的绝对值 == 列差值的绝对值，表示（左斜 OR 右斜）冲突
由此，行，列，左斜，右斜是否冲突就可得到
取消标记时，只需要恢复 col[]（对列的标记），而不需要恢复 a[]（放置位置），因为 a[] 会被后续操作覆盖，但是 col 不会，需要手动恢复现场
坑：int flag = 0; 这个要放在 if(c[j] == 0) 里，如果放在外面，就算列已经被占了，也会进入下一步递归，平白多了许多无关结果
class Solution {
private:
vector<string> temp; // 临时答案
vector<vector<string>> ans;
int m;
int c[10]; // 标记该列（已放置）
int a[10]; // 位置, a[3] = 7 表示 (3, 7) 已放置
// 第 r 行, 已放置 r 个皇后
void dfs(int r) {
// 递归出口
if (r == m) {
ans.push_back(temp);
return;
}
// 遍历每一列
for (int j = 0; j < m; ++j) {
if (c[j] == 0) { // 这一列未放置
int flag = 0; // 标记左斜 / 右斜 冲突
for (int i = 0; i < r; ++i) // 遍历前面已放置的每一行
if (abs(r - i) == abs(j - a[i])) {
flag = 1;
break;
}
// 不冲突，(r, j) 可以放置
if (flag == 0) {
a[r] = j; // 放置
string s = string(m, '.');
s[j] = 'Q';
temp.push_back(s);
c[j] = 1; // 标记（列）
dfs(r + 1);
c[j] = 0; // 取消标记
temp.pop_back(); // 恢复现场
}
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
m = n; // m 个皇后
dfs(0);
return ans;
}
};
