# 算法细节系列（23）：回溯

## Leetcode 093: Restore IP address

```    public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
backTrack(ans, "", 3, s, 0);
return ans;
}

private void backTrack(List<String> ans, String ip, int k, String address, int index){
if (k == 0){
if (valid(address.substring(index))){
ip += address.substring(index);
ans.add(ip);
return;
}
} else {
for (int i = 0; i < 3; i++) {
if (index + i >= address.length())
continue;
String cut = address.substring(index, index + i + 1);
if (valid(cut)) {
ip += cut + ".";
backTrack(ans, ip, k - 1, address, index + i + 1);
ip = ip.substring(0, ip.length() - (i + 1) - 1);
}
}
}
}

private boolean valid(String s){
if (s.length() >= 4 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1))
return false;
return Integer.parseInt(s) >= 0 && Integer.parseInt(s) <= 255;
}```

```public List<String> restoreIpAddresses(String s) {
List<String> ans = new ArrayList<>();
for (int i = 1; i < 4; i++){
if (i >= s.length()) continue;
for (int j = i + 1; j < i + 4; j++){
if (j >= s.length()) continue;
for (int k = j + 1; k < j + 4; k++){
if (k >= s.length()) continue;
String s1 = s.substring(0, i);
String s2 = s.substring(i, j);
String s3 = s.substring(j, k);
String s4 = s.substring(k);
if (valid(s1) && valid(s2) && valid(s3) && valid(s4)){
ans.add(s1+"."+s2+"."+s3+"."+s4);
}
}
}
}

return ans;
}```

## Leetcode 037: Sudoku Solver

```public void solveSudoku(char[][] board) {
backTrack(board);
}

private boolean backTrack(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (backTrack(board)) {
return true;
} else {
board[i][j] = '.';
}
}
}
//说明遍历了1-9都没找到答案 直接false即可
return false;
}
}
}
return true;
}

private boolean isValid(char[][] board, int row, int col, char c) {
for (int i = 0; i < 9; i++) {
if (board[i][col] != '.' && board[i][col] == c)
return false;
if (board[row][i] != '.' && board[row][i] == c)
return false;
if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
&& board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
return false;
}
return true;
}```

leetcode的测试数据中不存在多解的情况，所以一旦solve直接范围true即可，而如果尝试了1-9之后都没解决，那只能返回false了。

## Leetcode 051: N-Queens

```斜对角表示法：
int diag = row + col;

0 1 2 3
0 . . . X
1 . . X .
2 . X . .
3 X . . .

int diag = row - col + len;

-3 -2 -1 -0
0  X  .  .  .
1  .  X  .  .
2  .  .  X  .
3  .  .  .  X

```public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] cs = new char[n][n];
for (int i = 0; i < n; i++){
Arrays.fill(cs[i], '.');
}

boolean[] cols = new boolean[n];
boolean[] diag = new boolean[2*n];
boolean[] riag = new boolean[2*n];
backTrack(ans, cs, n, 0, cols, diag, riag);
return ans;
}

private void backTrack(List<List<String>> ans, char[][] path, int n, int start, boolean[] cols, boolean[] diag, boolean[] riag){
if (start == n){
List<String> pp = new ArrayList<>();
for (int i = 0; i < path.length; i++){
pp.add(new String(path[i]));
}
ans.add(new ArrayList<>(pp));
return;
}else{
for (int i = 0; i < n; i++){
if (!cols[i] && !diag[start + i] && !riag[start-i+n]){
path[start][i] = 'Q';
cols[i] = true;
diag[start + i] = true;
riag[start - i + n] = true;
backTrack(ans, path, n, start+1, cols, diag, riag);
path[start][i] = '.';
cols[i] = false;
diag[start + i] = false;
riag[start - i + n] = false;
}
}
}
}```

```public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[i].length; j++){
if(board[i][j] == words[0]){
board[i][j] = '#';
if (helper(board, i, j, words, 1)) return true;
board[i][j] = words[0];
}
}
}
return false;
}

int[][] dir = {{1,0},{-1,0},{0,-1},{0,1}};

private boolean helper(char[][] board, int x, int y, char[] words, int pos) {
if (pos == words.length) {
return true;
} else {
int row = board.length, col = board[0].length;
for (int[] d : dir){
int nx = x + d[0];
int ny = y + d[1];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && board[nx][ny] != '#' && board[nx][ny] == words[pos]){
board[nx][ny] = '#';
if(helper(board, nx, ny, words, pos+1)) return true;
board[nx][ny] = words[pos];
}
}
}
return false;
}```

## Leetcode 212: Word Seach II

```words = ["aaabcc","aaabcd","aaabce"]

"aaabcc"是它们的公共前缀，所以让board去check这个前缀是否存在，如果存在，在去递归check：
"c","d","e"的路径，存在返回。

```public List<String> findWords(char[][] board, String[] words) {
List<String> ans = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[i].length; j++){
dfs(board, i, j, root, ans);
}
}
return ans;
}

private void dfs(char[][] board, int i, int j, TrieNode root, List<String> ans){
char c = board[i][j];
if (c == '#' || root.next[c-'a'] == null) return;
root = root.next[c-'a'];
if (root.word != null){
ans.add(root.word);
root.word = null;
}

board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,root, ans);
if (j > 0) dfs(board, i, j - 1, root, ans);
if (i < board.length - 1) dfs(board, i + 1, j, root, ans);
if (j < board[0].length - 1) dfs(board, i, j + 1, root, ans);
board[i][j] = c;
}

private class TrieNode{
TrieNode[] next = new TrieNode[26];
String word;
}

private TrieNode buildTrie(String[] words){
TrieNode root = new TrieNode();
for (String w : words){
TrieNode p = root;
for (char c : w.toCharArray()){
int i = c- 'a';
if (p.next[i] == null) p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = w;
}
return root;
}```

## Leetcode 211: Add and Seach Word - Data Structure Design

```public class WordDictionary {

private class TrieNode {
TrieNode[] next = new TrieNode[26];
String word;
}

TrieNode root;

public WordDictionary() {
root = new TrieNode();
}

public void addWord(String word) {
TrieNode p = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (p.next[i] == null)
p.next[i] = new TrieNode();
p = p.next[i];
}
p.word = word;
}

public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}

private boolean match(char[] chs, int pos, TrieNode node){
if (pos == chs.length) return node.word != null;
if (chs[pos] != '.'){
return node.next[chs[pos]-'a'] != null && match(chs, pos+1, node.next[chs[pos]-'a']);
}else{
for (char c = 'a'; c <= 'z'; c++){
if (node.next[c-'a'] != null){
if(match(chs, pos+1, node.next[c-'a'])){
return true;
}
}
}
}
return false;
}

public static void main(String[] args) {
WordDictionary wd = new WordDictionary();
wd.addWord("bad");
wd.addWord("dad");
wd.addWord("mad");
wd.search("pad");
wd.search("bad");
wd.search(".ad");
wd.search("b..");
}
}```

0 条评论

• ### LeetCode Weekly Contest 35解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 33解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LWC 63: 749. Contain Virus

Problem: A virus is spreading rapidly, and your task is to quarantine the infec...

• ### 消灭 Java 代码的“坏味道”

代码中的"坏味道"，如"私欲"如"灰尘"，每天都在增加，一日不去清除，便会越累越多。如果用功去清除这些"坏味道"，不仅能提高自己的编码水平，也能使代码变得"精白...

• ### 消灭 Java 代码的“坏味道”

代码中的"坏味道"，如"私欲"如"灰尘"，每天都在增加，一日不去清除，便会越累越多。如果用功去清除这些"坏味道"，不仅能提高自己的编码水平，也能使代码变得"精白...

• ### MySql “找不到请求的 .Net Framework 数据提供程序。可能没有安装。”

需要在app.config或者web.config中添加下面的配置项 <system.data>     <DbProviderFactories> ...

• ### 消灭 Java 代码的“坏味道”

代码中的"坏味道"，如"私欲"如"灰尘"，每天都在增加，一日不去清除，便会越累越多。如果用功去清除这些"坏味道"，不仅能提高自己的编码水平，也能使代码变得"精白...

• ### 消灭 Java 代码的“坏味道”

代码中的"坏味道"，如"私欲"如"灰尘"，每天都在增加，一日不去清除，便会越累越多。如果用功去清除这些"坏味道"，不仅能提高自己的编码水平，也能使代码变得"精白...

• ### 【每日一题】37. Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.