Letter Combinations of a Phone Number - LeetCode
子集问题,从多重循环到回溯
用一个path记录
回溯三问:
dfs(i)->dfs(i + 1)
这题要注意idx是我们遍历的数字的位数,backtracking的时候要到下一层就是下一个数字,每个数字都是不同得集合,这题是求不同集合得组合.
Time: O(n*4^n)
Space: O(n)
class Solution {
String[] keypad = new String[]{"", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.length() == 0) return res;
StringBuilder sb = new StringBuilder();
backtracking(res, sb, digits, 0);
return res;
}
private void backtracking(List<String> res, StringBuilder sb, String digits, int idx) {
if (idx == digits.length()) {
res.add(sb.toString());
return;
}
String key = keypad[digits.charAt(idx) - '0'];
for (int i = 0; i < key.length(); i++) {
sb.append(key.charAt(i));
backtracking(res, sb, digits, idx + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
Restore IP Addresses - LeetCode
判断isValid的地方,要注意细节
Time: O(3^4)
Space: O(n)
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
StringBuilder sb = new StringBuilder(s);
backtracking(res, sb, 0, 0);
return res;
}
private void backtracking(List<String> res, StringBuilder sb, int points, int idx) {
if (points == 3) {
if (isValid(sb, idx, sb.length() - 1)) {
res.add(sb.toString());
}
return;
}
for (int i = idx; i < sb.length(); i++) {
if (isValid(sb, idx, i)) {
sb.insert(i + 1, '.');
points += 1;
backtracking(res, sb, points, i + 2);
sb.deleteCharAt(i + 1);
points -= 1;
}
}
}
private boolean isValid(StringBuilder sb, int left, int right) {
if (left > right) return false;
if (sb.charAt(left) == '0' && left != right) return false;
int num = 0;
for (int i = left; i <= right; i++) {
if (sb.charAt(i) < '0' || sb.charAt(i) > '9') return false;
int digit = sb.charAt(i) - '0';
num = num * 10 + digit;
if (num > 255) return false;
}
return true;
}
}
N-Queens - LeetCode
因为在单层搜索的过程中,每一层递归,只会选for循环(也就是同一行)里的一个元素,所以不用去重了。
Time: O(n!)
Space: O(n)
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] chess = new char[n][n];
for (char[] c : chess) {
Arrays.fill(c, '.');
}
backtracking(res, chess, n, 0);
return res;
}
private void backtracking(List<List<String>> res, char[][] chess, int n, int row) {
if (row == n) {
res.add(construct(chess));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(row, i, n, chess)) {
chess[row][i] = 'Q';
backtracking(res, chess, n, row + 1);
chess[row][i] = '.';
}
}
}
private boolean isValid(int row, int col, int n, char[][] chess) {
for (int i = 0; i < row; i++) {
if (chess[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chess[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++ ) {
if (chess[i][j] == 'Q') return false;
}
return true;
}
private List<String> construct(char[][] chess) {
List<String> path = new ArrayList<>();
for (int i = 0; i < chess.length; i++) {
path.add(new String(chess[i]));
}
return path;
}
}