1.分割回文串
- 每一个结点表示剩余没有扫描到的字符串，产生分支是截取了剩余字符串的前缀；
- 产生前缀字符串的时候，判断前缀字符串是否是回文。
- 如果前缀字符串是回文，则可以产生分支和结点；
- 如果前缀字符串不是回文，则不产生分支和结点，这一步是剪枝操作。
- 在叶子结点是空字符串的时候结算，此时 从根结点到叶子结点的路径，就是结果集里的一个结果，使用深度优先遍历，记录下所有可能的结果。
- 使用一个路径变量 path 搜索，path 全局使用一个（注意结算的时候，要生成一个拷贝），因此在递归执行方法结束以后需要回溯，即将递归之前添加进来的元素拿出去；
- path 的操作只在列表的末端，因此合适的数据结构是栈。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<String>> partition(String s) {int len = s.length();List<List<String>> res = new ArrayList<>();if (len == 0) {return res;}// Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new ArrayDeque<Integer>();// 注意：只使用 stack 相关的接口Deque<String> stack = new ArrayDeque<>();char[] charArray = s.toCharArray();dfs(charArray, 0, len, stack, res);return res;}/*** @param charArray* @param index 起始字符的索引* @param len 字符串 s 的长度，可以设置为全局变量* @param path 记录从根结点到叶子结点的路径* @param res 记录所有的结果*/private void dfs(char[] charArray, int index, int len, Deque<String> path, List<List<String>> res) {if (index == len) {res.add(new ArrayList<>(path));return;}for (int i = index; i < len; i++) {// 因为截取字符串是消耗性能的，因此，采用传子串下标的方式判断一个子串是否是回文子串if (!checkPalindrome(charArray, index, i)) {continue;}path.addLast(new String(charArray, index, i + 1 - index));dfs(charArray, i + 1, len, path, res);path.removeLast();}}/*** 这一步的时间复杂度是 O(N)，优化的解法是，先采用动态规划，把回文子串的结果记录在一个表格里** @param charArray* @param left 子串的左边界，可以取到* @param right 子串的右边界，可以取到* @return*/private boolean checkPalindrome(char[] charArray, int left, int right) {while (left < right) {if (charArray[left] != charArray[right]) {return false;}left++;right--;}return true;}
}
2.被围绕的区域
题目分析：
这道题要将所有被 'X' 包围的 'O' 进行替换。
那么我们首先要来考虑什么情况下， 'O' 不会被 'X' 包围。那就是这个'O'是在矩阵的边界上或者和矩阵边界上的'O'可达的
本题给定的矩阵中有三种元素：
- 字母 X；
- 被字母 X 包围的字母 O；
- 没有被字母 X 包围的字母 O。
本题要求将所有被字母 X 包围的字母 O都变为字母 X ，但很难判断哪些 O 是被包围的，哪些 O 不是被包围的。
注意到题目解释中提到：任何边界上的 O 都不会被填充为 X。 我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说：
- 对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O；
- 最后我们遍历这个矩阵，对于每一个字母：
- 如果该字母被标记过，则该字母为没有被字母 X 包围的字母 O，我们将其还原为字母 O；
- 如果该字母没有被标记过，则该字母为被字母 X 包围的字母 O，我们将其修改为字母 X。
class Solution {int n, m;public void solve(char[][] board) {n = board.length;if (n == 0) {return;}m = board[0].length;for (int i = 0; i < n; i++) {dfs(board, i, 0);dfs(board, i, m - 1);}for (int i = 1; i < m - 1; i++) {dfs(board, 0, i);dfs(board, n - 1, i);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (board[i][j] == 'A') {board[i][j] = 'O';} else if (board[i][j] == 'O') {board[i][j] = 'X';}}}}public void dfs(char[][] board, int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {return;}board[x][y] = 'A';dfs(board, x + 1, y);dfs(board, x - 1, y);dfs(board, x, y + 1);dfs(board, x, y - 1);}
}
3.矩阵置零
思路和算法
我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
具体地，我们首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。最后我们再次遍历该数组，用标记数组更新原数组即可。
class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length;boolean[] row = new boolean[m];boolean[] col = new boolean[n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {row[i] = col[j] = true;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (row[i] || col[j]) {matrix[i][j] = 0;}}}}
}
