DFS + Backtracking
Last updated
Last updated
Basically, going back to the previous level and check the unvisited neighboring nodes. 顾名思义，回溯。即回到上一层查未查过的邻节点。
Brute force solution, usually to list all the possibilities. 暴力解法，穷举所有可能性
对于全局变量，如visited[][]，需在访问下一层之前置true，并在返回上一层之前置false
what to return when meet the termination conditions，如越界，无限循环（访问已访问过的节点），触底等
String[] dict = {"", "", "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 cur = new StringBuilder();
helper(digits, 0, cur, res);
return res;
}
private void helper(String digits, int index, StringBuilder sb, List<String> res) {
// base case
if (index == digits.length()) {
res.add(sb.toString());
return;
}
String chars = dict[digits.charAt(index) - '0'];
for (int i = 0; i < chars.length(); i++) {
sb.append(chars.charAt(i));
helper(digits, index + 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (candidates == null || candidates.length == 0) return res;
Arrays.sort(candidates);
List<Integer> cur = new ArrayList<>();
helper(candidates, 0, target, cur, res);
return res;
}
private void helper(int[] candidates, int index, int target, List<Integer> cur, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<Integer>(cur));
return;
}
for (int i = index; i < candidates.length; i++) {
if (target >= candidates[i]) {
cur.add(candidates[i]);
helper(candidates, i, target - candidates[i], cur, res);
cur.remove(cur.size() - 1);
}
}
}// Method 1
class Solution {
private int[][] dir1s = {{0,-1},{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1,1}, {1, 0}, {1,-1}};
private int[][] dir2s = {{0,-2},{-1,-2},{-2,-2},{-2,-1},{-2,0},{-2,1},{-2,2},{-1,2},{0,2},{1,2},{2,2},{2,1},{2,0},{2,-1},{2,-2}, {1,-2}};
public int numberOfPatterns(int m, int n) {
int ans = 0;
for (int i = m; i <= n; i++) {
boolean[][] visited = new boolean[3][3];
ans += 4 * helper(i - 1, 0, 1, visited);
ans += 4 * helper(i - 1, 0, 0, visited);
ans += helper(i - 1, 1, 1, visited);
}
return ans;
}
private int helper(int count, int row, int col, boolean[][] visited) {
if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length || visited[row][col]) {
return 0;
}
if (count == 0) {
return 1;
}
visited[row][col] = true;
int ans = 0;
for (int i = 0; i < dir1s.length; i++) {
int x = row + dir1s[i][0];
int y = col + dir1s[i][1];
ans += helper(count - 1, x, y, visited);
}
for (int i = 0; i < dir2s.length; i++) {
int x = row + dir2s[i][0];
int y = col + dir2s[i][1];
if (row == x && !visited[row][1]) {
continue;
} else if (col == y && !visited[1][col]) {
continue;
}
if (x + row == 2 && y + col == 2 && !visited[1][1]) {
continue;
}
ans += helper(count - 1, x, y, visited);
}
visited[row][col] = false;
return ans;
}
}
/*
* Method 2
* Optimized validity checking with the help of skip matrix
int[][] skip = new int[10][10];
skip[1][3] = skip[3][1] = 2;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][7] = skip[7][1] = 4;
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[6][4] = skip[4][6] = 5;
*/class Solution {
private char[][] pairs = {{'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}};
public List<String> findStrobogrammatic(int n) {
List<String> ans = new ArrayList<>();
if (n == 0) return ans;
char[] array = new char[n];
helper((n - 1) / 2, n / 2, array, ans);
return ans;
}
private void helper(int left, int right, char[] array, List<String> ans) {
if (left < 0) {
ans.add(new String(array));
return;
}
if (left == right) {
for (int i = 0; i < 3; i++) {
char tmpLeft = array[left];
array[left] = pairs[i][0];
helper(left - 1, right + 1, array, ans);
array[left] = tmpLeft;
}
} else if (left > 0) {
for (int i = 0; i < pairs.length; i++) {
char tmpLeft = array[left];
char tmpRight = array[right];
array[left] = pairs[i][0];
array[right] = pairs[i][1];
helper(left - 1, right + 1, array, ans);
array[left] = tmpLeft;
array[right] = tmpRight;
}
} else if (left == 0) {
for (int i = 1; i < pairs.length; i++) {
char tmpLeft = array[left];
char tmpRight = array[right];
array[left] = pairs[i][0];
array[right] = pairs[i][1];
helper(left - 1, right + 1, array, ans);
array[left] = tmpLeft;
array[right] = tmpRight;
}
}
}
}// 按长度，穷举所有可能性
// 注意终止条件（长度相等且在范围内），以及 如何判断number是否有效
class Solution {
private char[][] pairs = {{'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}};
public int strobogrammaticInRange(String low, String high) {
int[] ans = new int[] { 0 };
for (int length = low.length(); length <= high.length(); length++) {
char[] array = new char[length];
helper(0, length - 1, array, low, high, ans);
}
return ans[0];
}
// Return the number of valid stro numbers of certain length
private void helper(int left, int right, char[] array, String low, String high, int[] ans) {
if (left > right) {
String cur = new String(array);
if ((cur.length() == low.length() && cur.compareTo(low) < 0) ||
(cur.length() == high.length() && cur.compareTo(high) > 0)) {
return;
}
ans[0]++;
return;
}
for (char[] pair: pairs) {
array[left] = pair[0];
array[right] = pair[1];
if (array.length != 1 && array[0] == '0') {
continue;
}
if (left == right && pair[0] != pair[1]) {
continue;
}
helper(left + 1, right - 1, array, low, high, ans);
}
}
}// 首先，扫一遍string，得到需要删除的 ( 和 ) 数量。
// 再用 DFS 寻找满足条件，即有效的，并且唯一的，substring。
// 这里关键的点在于剪枝，如果在寻找的过程中需要删除的 '(' 小于 0 或
// 需要删除的 ')' 小于0 或
// 当前构成的substring invalid，则直接返回。
public List<String> removeInvalidParentheses(String s) {
int leftToRemove = 0, rightToRemove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
leftToRemove += 1;
} else if (s.charAt(i) == ')') {
if (leftToRemove == 0) {
rightToRemove += 1;
} else {
leftToRemove -= 1;
}
}
}
Set<String> ans = new HashSet<>();
StringBuilder sb = new StringBuilder();
dfs(s, 0, leftToRemove, rightToRemove, 0, sb, ans);
return new ArrayList<String>(ans);
}
private void dfs(String s, int curIndex, int leftToRemove, int rightToRemove, int valid, StringBuilder sb, Set<String> ans) {
if (leftToRemove < 0 || rightToRemove < 0 || valid < 0) {
return;
}
if (curIndex == s.length()) {
if (leftToRemove == 0 && rightToRemove == 0 && valid == 0) {
ans.add(sb.toString());
}
return;
}
char c = s.charAt(curIndex);
int length = sb.length();
if (c == '(') {
dfs(s, curIndex + 1, leftToRemove - 1, rightToRemove, valid, sb, ans); // not use '('
dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid + 1, sb.append(c), ans); // use '('
} else if (c == ')') {
dfs(s, curIndex + 1, leftToRemove, rightToRemove - 1, valid, sb, ans); // not use ')'
dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid - 1, sb.append(c), ans); // use ')'
} else {
dfs(s, curIndex + 1, leftToRemove, rightToRemove, valid, sb.append(c), ans); // use letters
}
sb.setLength(length);
}// 思路很巧妙，利用 BFS 找最短路径的思想，从input string出发，以删除的个数为depth。
// 对于每层不同的 node，将所有删除一个'('或')'的子字符串作为child node存进queue。
// 直到找到 valid 的 node，就无需再往下走，因为已经不是minimum deletion了。
public List<String> removeInvalidParentheses(String s) {
List<String> ans = new ArrayList<>();
Set<String> visited = new HashSet<>();
Deque<String> queue = new LinkedList<>();
queue.add(s);
visited.add(s);
while (!queue.isEmpty()) {
int size = queue.size();
int ansSize = ans.size();
while (size-- > 0) {
String cur = queue.pollFirst();
if (isValid(cur)) {
ans.add(cur);
} else {
for (int i = 0; i < cur.length(); i++) {
if (cur.charAt(i) == '(' || cur.charAt(i) == ')') {
String next = cur.substring(0, i) + cur.substring(i + 1);
if (!visited.contains(next)) {
queue.add(next);
visited.add(next);
}
}
}
}
}
if (ans.size() > ansSize) {
break;
}
}
return ans;
}
private boolean isValid(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') count++;
if (s.charAt(i) == ')') count--;
if (count < 0) return false;
}
return count == 0;
}