一劣纲、電話號碼的字母組合

• 不同電話號碼映射不同的字母組

  • 需要保存

• 遞歸函數(shù)處理：

  • 每一層對應(yīng)一個電話號碼：循環(huán)操作其對應(yīng)的字母組
  • 一層遞歸循環(huán)傳入電話號碼對應(yīng)的字母組
  • 調(diào)用遞歸函數(shù)特恬，傳入的字母下標(biāo)需增加舷暮，字母組合加上當(dāng)前循環(huán)的字母組中的字母
  • 結(jié)束：當(dāng)前字母組循環(huán)結(jié)束、或者 組合長度等于digital的長度+

• String字符串拼接和StringBuilder.append()的效率問題_穆呈祥的博客-CSDN博客

  拼接字符串的效率問題（String嚼锄，StringBuffer爷辱，StringBuilder對比） - 時光.漫步 - 博客園 (cnblogs.com)

• 執(zhí)行時間 5ms的String + 代碼：

  class Solution {
      public List<String> letterCombinations(String digits) {
          List<String> ans =  new ArrayList<>();
          if(digits.length() > 0) {
              checkBack(ans, digits, 0, "", getMap());
          }
          return ans;
      }
  
      private void checkBack(List<String> ans, String digits, int index, String combination, HashMap<Character, char[]> map) {
          if(combination.length() == digits.length()) {
              ans.add(combination);
          } else {
              char t = digits.charAt(index);
              char[] charArr = map.get(t);
              for(int i = 0; i < charArr.length; i++) {
                  checkBack(ans, digits, index + 1, combination + charArr[i], map);
              }
          }
      }
  
      private HashMap<Character, char[]> getMap() {
          HashMap<Character, char[]> map = new HashMap<>();
          map.put('2', new char[] {'a', 'b', 'c'});
          map.put('3', new char[] {'d', 'e', 'f'});
          map.put('4', new char[] {'g', 'h', 'i'});
          map.put('5', new char[] {'j', 'k', 'l'});
          map.put('6', new char[] {'m', 'n', 'o'});
          map.put('7', new char[] {'p', 'q', 'r', 's'});
          map.put('8', new char[] {'t', 'u', 'v'});
          map.put('9', new char[] {'w', 'x', 'y', 'z'});
          return map;
      }
  }
  

• 執(zhí)行用時 0ms的StringBulider代碼：

  class Solution {
      public List<String> letterCombinations(String digits) {
          List<String> ans =  new ArrayList<>();
          if(digits != null && digits.length() > 0) {
              checkBack(ans, digits, 0, new StringBuilder(), getMap());
          }
          return ans;
      }
  
      private void checkBack(List<String> ans, String digits, int index, StringBuilder combination, HashMap<Character, char[]> map) {
          if(combination.length() == digits.length()) {
              ans.add(combination.toString());
          } else {
              char t = digits.charAt(index);
              char[] charArr = map.get(t);
              for(int i = 0; i < charArr.length; i++) {
                  checkBack(ans, digits, index + 1, combination.append(charArr[i]), map);
                  combination.deleteCharAt(combination.length() - 1);
              }
          }
      }
  
      private HashMap<Character, char[]> getMap() {
          HashMap<Character, char[]> map = new HashMap<>();
          map.put('2', new char[] {'a', 'b', 'c'});
          map.put('3', new char[] {'d', 'e', 'f'});
          map.put('4', new char[] {'g', 'h', 'i'});
          map.put('5', new char[] {'j', 'k', 'l'});
          map.put('6', new char[] {'m', 'n', 'o'});
          map.put('7', new char[] {'p', 'q', 'r', 's'});
          map.put('8', new char[] {'t', 'u', 'v'});
          map.put('9', new char[] {'w', 'x', 'y', 'z'});
          return map;
      }
  }
  

• 不僅時間上耗時不同晕翠，內(nèi)存同樣是不同，StringBuilder比String+ 少消耗內(nèi)存

二担映、括號生成

• 組合問題

• n代表有 n對括號

  • 首先獲得所有括號組合
  • 考慮去除無效括號：
    • 去除條件：左括號可用數(shù)量大于0废士、右括號未使用數(shù)量大于左括號

• class Solution {
      public List<String> generateParenthesis(int n) {
          List<String> ans = new ArrayList<>();
          checkBack(ans, n * 2, n, n, new StringBuilder());
          return ans;
      }
  
      private void checkBack(List<String> ans, int n, int left, int right, StringBuilder combination) {
          if(n <= 0) {
              ans.add(combination.toString());
          } else {
              //左括號可用數(shù)量大于0
              if(left > 0) {
                  checkBack(ans, n - 1, left - 1, right, combination.append('('));
                  combination.deleteCharAt(combination.length() - 1);
              }
              //右括號未使用數(shù)量大于左括號
              if(right > left) {
                  checkBack(ans, n - 1, left, right - 1, combination.append(')'));
                  combination.deleteCharAt(combination.length() - 1);
              }
          }
      }
  }
  

三、單詞搜索

• 深度優(yōu)先搜索：第一個字符在數(shù)組中蝇完，就開始深度搜索

• 四個方向都要檢查

• 利用記憶數(shù)組確定該元素是否還可作為單詞部分

• class Solution {
      public boolean exist(char[][] board, String word) {
          for(int i = 0; i < board.length; i++) {
              for(int j = 0; j < board[0].length; j++) {
                  if(word.charAt(0) == board[i][j] && checkBack(board, word, 0, new int[board.length][board[0].length], i, j)) {
                      return true;
                  }
              }
          }
          return false;
      }
  
      private boolean checkBack(char[][] board, String word, int index, int[][] memory, int i, int j) {
          if(index == word.length()) {
              return true;
          }
          if(i >= 0 && i < board.length && j >= 0 && j < board[0].length && memory[i][j] == 0 && index < word.length() && board[i][j] == word.charAt(index)) {
              memory[i][j] = 1;
              boolean ans =  checkBack(board, word, index + 1, memory, i - 1, j) ||
                      checkBack(board, word, index + 1, memory, i + 1, j) ||
                      checkBack(board, word, index + 1, memory, i, j - 1) ||
                      checkBack(board, word, index + 1, memory, i, j + 1);
              memory[i][j] = 0;
              return ans;
          }
          return false;
      }
  }