算法基础第11天

17. 电话号码的字母组合

/**
 17. 电话号码的字母组合
 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

 示例 1：

 输入：digits = "23"
 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 示例 2：

 输入：digits = ""
 输出：[]
 示例 3：

 输入：digits = "2"
 输出：["a","b","c"]


 提示：

 0 <= digits.length <= 4
 digits[i] 是范围 ['2', '9'] 的一个数字。

 * @author zeroheart
 *
 */
public class Question17 {
    private List<String> res = new ArrayList<>();
    private StringBuilder path  = new StringBuilder();
    private String[] chars = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

    public List<String> letterCombinations(String digits) {
        backtracting(digits, chars, 0);
        return res;
    }

    private void backtracting(String digits, String[] chars,  int x) {
        if(path.length() == digits.length()){
            String s = path.toString();
            res.add(s);
            System.out.println(s);
            return;
        }

        String aChar = chars[digits.charAt(x)-'0'];
        int length = aChar.length();
        for(int j = 0; j<length; j++){
            path.append(aChar.charAt(j));
            backtracting(digits, chars, x+1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public static void main(String[] args) {
        new Question17().letterCombinations("23");
    }
}

22. 括号生成

/**
 22. 括号生成
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。



 示例 1：

 输入：n = 3
 输出：["((()))","(()())","(())()","()(())","()()()"]
 示例 2：

 输入：n = 1
 输出：["()"]


 提示：

 1 <= n <= 8

 * @author zeroheart
 *
 */
public class Question22 {
    private List<String> res = new ArrayList<>();
    private StringBuilder path  = new StringBuilder();

    public List<String> generateParenthesis(int n) {
        backtracting(n, n);
        return res;
    }

    private void backtracting(int left, int right) {
        if(left == 0 && right == 0){
            String s = path.toString();
            res.add(s);
            System.out.println(s);
            return;
        }

        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }

        if(left>0){
            path.append("(");
            backtracting(left-1, right);
            path.deleteCharAt(path.length() - 1);
        }

        if(right>0){
            path.append(")");
            backtracting(left, right-1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public static void main(String[] args) {
        new Question22().generateParenthesis(3);
    }
}

79. 单词搜索

/**
 79. 单词搜索
 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

 示例 1：

 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 输出：true
 示例 2：


 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
 输出：true
 示例 3：


 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
 输出：false


 提示：

 m == board.length
 n = board[i].length
 1 <= m, n <= 6
 1 <= word.length <= 15
 board 和 word 仅由大小写英文字母组成


 * @author zeroheart
 *
 */
public class Question79 {
    private int pos = 0;
    private boolean res = false;
    private boolean[][] visited;
    public boolean exist(char[][] board, String word) {

        int m = board.length;
        int n = board[0].length;

        visited = new boolean[m][n];
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                backtracting(i, j, pos, m, n, board, word);
            }
        }

        return res;
    }


    private void backtracting(int i, int j, int pos, int m, int n, char[][] board, String word) {
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j]
                || word.charAt(pos)!=board[i][j]) { // 这个开始忘记写了。。。。
            return;
        }

        if(pos == word.length()-1){
            res = true;
            return;
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        visited[i][j] = true;
        for(int x = 0; x < 4; x++){
            backtracting(i+dx[x], j+dy[x], pos+1, m, n, board, word);
        }
        visited[i][j] = false;
    }
}