LeetCode题解--回溯算法(一)

妖狐艹你老母 2023-06-20 06:01 15阅读 0赞

## 17. 电话号码的字母组合 ##

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

![format_png][]  
示例:

输入：“23”  
输出：\[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”\].  
说明:  
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

### 回溯算法 ###

class Solution {
        
        Map<String, String> map = new HashMap<String, String>() {
        {
        
            put("2", "abc");
            put("3", "def");
            put("4", "ghi");
            put("5", "jkl");
            put("6", "mno");
            put("7", "pqrs");
            put("8", "tuv");
            put("9", "wxyz");
        }};
        List<String> out = new ArrayList<String>();
        private void backtrack(String combination, String digits){
        
            if (digits.length() == 0){
        
                out.add(combination);
            } else {
        
                String digit = digits.substring(0, 1);
                String letters = map.get(digit);
                for (int i = 0; i < letters.length(); ++i){
        
                    String letter = letters.substring(i, i + 1);
                    backtrack(combination + letter, digits.substring(1));
                }
            }
        }
        public List<String> letterCombinations(String digits) {
        
            if (digits.length() != 0){
        
                backtrack("", digits);
            }
            return out;
        }
    }

## 93. 复原IP地址 ##

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: “25525511135”  
输出: \[“255.255.11.135”, “255.255.111.35”\]

### 回溯 ###

![format_png 1][]

class Solution {
        
        private String s;
        private int n;
        LinkedList<String> segments = new LinkedList<String>();
        ArrayList<String> output = new ArrayList<String>();
        private boolean valid(String segment) {
        
            int m = segment.length();
            if (m > 3) {
        
                return false;
            }
            return (segment.charAt(0) != '0') ? (Integer.valueOf(segment) <= 255) : (m == 1);
        }
        private void update_output(int cur_pos) {
        
            String segment = s.substring(cur_pos + 1, n);
            if (valid(segment)) {
        
                segments.add(segment);
                output.add(String.join(".", segments));
                segments.removeLast();
            }
        }
        private void backtrack(int prep, int dots){
        
            int max_pos = Math.min(n - 1, prep + 4);
            for (int cur_pos = prep + 1; cur_pos < max_pos; ++cur_pos){
        
                String segment = s.substring(prep + 1, cur_pos + 1);
                if (valid(segment)){
        
                    segments.add(segment);
                    if (dots - 1 == 0){
        
                        update_output(cur_pos);
                    } else {
        
                        backtrack(cur_pos, dots - 1);
                    }
                    segments.removeLast();
                }
            }
        }
        public List<String> restoreIpAddresses(String s) {
        
            n = s.length();
            this.s = s;
            backtrack(-1, 3);
            return output;
        }
    }

## 79. 单词搜索 ##

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =  
\[  
\[‘A’,‘B’,‘C’,‘E’\],  
\[‘S’,‘F’,‘C’,‘S’\],  
\[‘A’,‘D’,‘E’,‘E’\]  
\]

给定 word = “ABCCED”, 返回 true.  
给定 word = “SEE”, 返回 true.  
给定 word = “ABCB”, 返回 false.

### 回溯算法 ###

class Solution {
        
        private int m, n;
        private int[][] direction = {
        {
        1, 0}, {
        -1, 0}, {
        0, 1}, {
        0, -1}};
        public boolean exist(char[][] board, String word) {
        
            if (word == null || word.length() == 0) {
        
                return true;
            }
            if (board == null || board.length == 0 || board[0].length == 0) {
        
                return false;
            }
            m = board.length;
            n = board[0].length;
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; ++i) {
        
                for (int j = 0; j < n; ++j) {
        
                    if (dfs(0, i, j, visited, board, word)) {
        
                        return true;
                    }
                }
            }
            return false;
        }
        private boolean dfs(int curLen, int r, int c, boolean[][] visited, char[][] board, String word){
        
            if (curLen == word.length()) {
        
                return true;
            }
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) {
        
                return false;
            }
            visited[r][c] = true;
            for (int[] d : direction) {
        
                if (dfs(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
        
                    return true;
                }
            }
            visited[r][c] = false;
            return false;
        }
    }

## 257. 二叉树的所有路径 ##

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

1  
/  
2 3  
  
5

输出: \[“1->2->5”, “1->3”\]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private void backtrack(TreeNode node, List<String> ans, List<Integer> values) {
        
            if (node == null) {
        
                return;
            }
            values.add(node.val);
            if (isLeaf(node)) {
        
                ans.add(buildPath(values));
            } else {
        
                backtrack(node.left, ans, values);
                backtrack(node.right, ans, values);
            }
            values.remove(values.size() - 1);
        }
        private boolean isLeaf(TreeNode node) {
        
            return node.left == null && node.right == null;
        }
        public List<String> binaryTreePaths(TreeNode root) {
        
            List<String> ans = new ArrayList<String>();
            if (root == null){
        
                return ans;
            }
            List<Integer> values = new ArrayList<Integer>();
            backtrack(root, ans, values);
            return ans;
        }
        private String buildPath(List<Integer> values) {
        
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < values.size(); ++i){
        
                str.append(values.get(i));
                if (i != values.size() - 1) {
        
                    str.append("->");
                }
            }
            return str.toString();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GaGVLRkU2ZUpOMlRQcERwV2NUM3Y5SGFoV3hr?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gb2ZtVWFWeGdhZEpkSGItZndfS3poUE1aX21o?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191207194906779.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhcmRzZXB0ZW1iZXI=,size_16,color_FFFFFF,t_70