LeetCode题解 20(17，79) 电话号码的字母组合,单词搜索＜回溯＞

电话号码的字母组合(17)

思路: 根据题意我们必须根据数字获取对应的字符数组，因此我们先定义1个字符数组表示这个电话表

private String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

接着我们定义结果集,同时我们对特殊case进行判断

List<String> res = new ArrayList<>();

        if(digits == null || digits.length() == 0){return res;}

回溯部分的思路(helper):
我们需要传入一个可变的字符串StringBuilder,因为StringBuilder的性能比较高,还要我们输入的数字digits。
我们可以看到 当我们输入2位数，显示出来的字符串长度也就是2，因此将这这个条件作为退出递归的条件，当满足这个条件时就将可变字符串加入结果集，也就是我们要的答案。

    public void helper(StringBuilder curr,String digits){if(curr.length() == digits.length()){res.add(curr.toString());return;}

我们要获取我们输入的每一个数字，从而获取对应的字符数组，

        int num = digits.charAt(curr.length())-'0';String s1 = letters[num];

遍历我们获取的整个字符数组，将它们依次加入可变字符串curr中，重复以上操作。

        for(char c : s1.toCharArray()){curr.append(c);helper(curr,digits);curr.deleteCharAt(curr.length()-1);}

代码解答

class Solution {private String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return res;}helper(new StringBuilder(),digits);return res;}public void helper(StringBuilder curr,String digits){if(curr.length() == digits.length()){res.add(curr.toString());return;}int num = digits.charAt(curr.length())-'0';String s1 = letters[num];for(char c : s1.toCharArray()){curr.append(c);helper(curr,digits);curr.deleteCharAt(curr.length()-1);}}
}

单词搜索(79)

这道题就是它给了我们一个二维数组，我们需要去根据我们输入的字符串去找在这个表格中接连出现的。如果有就返回true。
思路:
我需要先获取这个二位数组的长，宽，我们输入字符串的长度，并且我们将这个二维数组，变成布尔类型的字符数组,当检查到一个就将此位置置为true。我们定义方法search去搜索，传入的参数分别是i，j，(start)0为我们输入的字符串的字符数组的起始索引。

class Solution {//先定义长和宽int m;int n;int w;char[] letters;char[][] board;boolean[][] visted;public boolean exist(char[][] board, String word) {this.m = board.length;this.n = board[0].length;this.w = word.length();this.letters = word.toCharArray();this.board = board;this.visted = new boolean[m][n];for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){//0是字符串数组的起始索引boolean res = search(i,j,0);if(res){return true;}}}return false;}

当我们的start到达了数组的最大长度，就表示我们整个字符串都已经遍历完成，这时就返回true。
当我们的i，j不在二维数组里面也就是说出边界了，或者某个字符不等于二维数组里面的字符。这时通通返回false。

        if(i<0 || j<0 || i>=m || j>=n || letters[start] != board[i][j]){return false;}

接着我们去遍历二维数组每四个方向

boolean res = search(i+1,j,start+1) || search(i,j+1,start+1) || search(i-1,j,start+1) ||search(i,j-1,start+1);

代码解答

class Solution {//先定义长和宽int m;int n;int w;char[] letters;char[][] board;boolean[][] visted;public boolean exist(char[][] board, String word) {this.m = board.length;this.n = board[0].length;this.w = word.length();this.letters = word.toCharArray();this.board = board;this.visted = new boolean[m][n];for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){//0是字符串数组的起始索引boolean res = search(i,j,0);if(res){return true;}}}return false;}public boolean search(int i,int j,int start){if(start >= w){return true;}if(i<0 || j<0 || i>=m || j>=n || letters[start] != board[i][j]){return false;}board[i][j] += 52;boolean res = search(i+1,j,start+1) || search(i,j+1,start+1) || search(i-1,j,start+1) ||search(i,j-1,start+1);board[i][j] -= 52;return res;}
}