Hot100中的回溯探寻

探寻Hot100中的回溯解法

单词搜索（079）

class Solution {
    int m, n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        char[] words = word.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backTrace(0, i, j, board, words)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backTrace(int idx, int row, int col, char[][] board, char[] words) {
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != words[idx]) {
            return false;
        }
        if (idx == words.length - 1) {
            return true;
        }
        board[row][col] = '0';
        boolean status = backTrace(idx + 1, row + 1, col, board, words) || backTrace(idx + 1, row, col + 1, board, words) ||
                backTrace(idx + 1, row - 1, col, board, words) || backTrace(idx + 1, row, col - 1, board, words);
        board[row][col] = words[idx];
        return status;
    }
}

• 分析
  这是一个基础的回溯应用，通过遍历矩阵的每个单元格，利用回溯来探索是否能找到匹配目标单词的路径。回溯过程中会标记已访问的位置，避免重复使用，并在探索完成后恢复状态。

分割回文串（131）

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backTrace(0, s);
        return res;
    }

    private void backTrace(int idx, String s) {
        if (idx == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = idx; j < s.length(); j++) {
            if (isPalindrome(idx, j, s)) {
                path.add(s.substring(idx, j + 1));
                backTrace(j + 1, s);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int left, int right, String s) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

• 分析
  利用回溯来尝试分割字符串，对于每个可能的子串位置，先判断是否为回文，如果是则将其加入当前路径并递归处理后续部分，回溯时移除最后加入的子串以尝试其他可能。

N皇后（051）

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        boolean[] column = new boolean[n];
        boolean[] diagRig = new boolean[2 * n];
        boolean[] diagLef = new boolean[2 * n];
        backTrace(0, queens, column, diagLef, diagRig);
        return res;
    }

    private void backTrace(int row, int[] queens, boolean[] column, boolean[] diagLef, boolean[] diagRig) {
        int n = column.length;
        if (row == n) {
            List<String> temp = new ArrayList<>(n);
            for (int col : queens) {
                char[] rowArr = new char[n];
                Arrays.fill(rowArr, '.');
                rowArr[col] = 'Q';
                temp.add(new String(rowArr));
            }
            res.add(temp);
            return;
        }
        for (int col = 0; col < n; col++) {
            int diagLefIdx = row - col + n - 1;
            if (!column[col] && !diagLef[diagLefIdx] && !diagRig[row + col]) {
                queens[row] = col;
                column[col] = diagLef[diagLefIdx] = diagRig[row + col] = true;
                backTrace(row + 1, queens, column, diagLef, diagRig);
                column[col] = diagLef[diagLefIdx] = diagRig[row + col] = false;
            }
        }
    }
}

• 分析
  N皇后问题需要满足行、列及两条对角线不冲突的条件。通过回溯法逐行尝试放置皇后，利用布尔数组标记列和对角线的占用情况，递归处理下一行并在回溯时恢复状态，最终将符合条件的皇后位置组合转换为结果列表中的字符串形式。