LintCode 425：电话号码的字母组合

https://www.lintcode.com/problem/letter-combinations-of-a-phone-number

描述

给一个不包含0和1的数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。
下图的手机按键图，就表示了每个数字可以代表的字母。

1 2
ABC		 3
DEF
4
GHI		 5
JKL		 6
MNO
7
PQRS		 8
TUV		 9
WXYZ

样例

  1. 输入: "23"
  2. 输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
  3. 解释: 
  4. '2' 可以是 'a', 'b' 或 'c'
  5. '3' 可以是 'd', 'e' 或 'f'
  7. 输入: "5"
  8. 输出: ["j", "k", "l"]

解题思路

简单深搜题

AC代码

  1. public class Solution {
  2.     // 每个数字代表的字母
  3.     String[] ss = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
  4.     // 存储字母组合
  5.     List<String> list = new LinkedList<>();
  7.     public List<String> letterCombinations(String digits) {
  8.         // 因为测试是用的一个对象，所以list需要清空一下
  9.         list.clear();
  10.         if (digits.equals(""))
  11.             return list;
  12.         // 深搜得到字母组合
  13.         assemble(0,digits,"");
  14.         return list;
  15.     }
  17.     private void assemble(int i, String digits, String s) {
  18.         // 已经找到一个组合，加入list，返回
  19.         if (i == digits.length()){
  20.             list.add(s);
  21.             return;
  22.         }        
  23.         char ch = digits.charAt(i);
  24.         String str = ss[((int) ch) - 48];
  25.         for (int j = 0; j < str.length(); j++) {
  26.             assemble(i + 1,digits,s + str.charAt(j));
  27.         }
  28.     }
  29. }

LintCode 10：字符串的不同排列

https://www.lintcode.com/problem/string-permutation-ii

描述

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。

样例

  1. 输入："abb"
  2. 输出：
  3. ["abb", "bab", "bba"]
  5. 输入："aabb"
  6. 输出：
  7. ["aabb", "abab", "baba", "bbaa", "abba", "baab"]

解题思路

简单的深搜

AC代码

  1. public class Solution {
  3.     List<String> list = new ArrayList<>();
  5.     public List<String> stringPermutation2(String str) {
  6.         list.clear();
  7.         if (str == null) { return list; }
  8.         // 转成字符数组更容易处理
  9.         char[] ch = str.toCharArray();
  10.         // 记录当前位置是否已经被选取至组合中
  11.         boolean[] flag = new boolean[ch.length];
  12.         // 构造组合
  13.         StringBuilder sb = new StringBuilder();
  14.         // 排序，去重考虑
  15.         Arrays.sort(ch);
  16.         // 深搜
  17.         dfs(sb, 0, ch, flag);
  18.         return list;
  19.     }
  21.     private void dfs(StringBuilder sb, int step, char[] ch, boolean[] flag) {
  22.         // 找到一个组合
  23.         if (step == ch.length) {
  24.             list.add(sb.toString());
  25.             return;
  26.         }
  28.         for (int i = 0; i < ch.length; i++) {
  29.             if (flag[i]) {  continue; }
  30.             // 去重，当有两个相同字母时，在当前层只取一次
  31.             if (i > 0 && ch[i] == ch[i - 1] && !flag[i - 1]) { continue; }
  32.             // 标准深搜过程
  33.             sb.append(ch[i]);
  34.             flag[i] = true;
  35.             dfs(sb, step + 1, ch, flag);
  36.             flag[i] = false;
  37.             sb.deleteCharAt(step);
  38.         }
  39.     }
  40. }

LintCode 135：数字组合

https://www.lintcode.com/problem/combination-sum/

描述

给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.
在同一个组合中, candidates 中的某个数字不限次数地出现.

  1. 所有数值 (包括 target ) 都是正整数.
  2. 返回的每一个组合内的数字必须是非降序的.
  3. 返回的所有组合之间可以是任意顺序.
  4. 解集不能包含重复的组合.

    样例

    ```java 输入: candidates = [2, 3, 6, 7], target = 7 输出: [[7], [2, 2, 3]]

输入: candidates = [1], target = 3 输出: [[1, 1, 1]]

  1. <a name="Tzght"></a>
  2. #### 解题思路
  3. 给数字集合排序，深搜
  4. <a name="lEvxt"></a>
  5. #### AC代码
  6. ```java
  7. public class Solution {
  8.     List<List<Integer>> list = new ArrayList<>();
  9.     int[] candidates;
  11.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  12.         // 排序
  13.         Arrays.sort(candidates);
  14.         List<Integer> li = new ArrayList<>();
  15.         this.candidates = candidates;
  16.         dfs( 0, 0, target, li);
  17.         return list;
  18.     }
  20.     private void dfs(int index, int add, int target, List<Integer> li) {
  21.         if (add == target) {
  22.             list.add(new ArrayList<>(li));
  23.             return;
  24.         }
  25.         for (int i = index; i < candidates.length; i++) {
  26.             // 去重
  27.             if (i > 0 && candidates[i] == candidates[i - 1]) {
  28.                 continue;
  29.             }
  30.             if (add + candidates[i] > target) {
  31.                 break;
  32.             }
  33.             li.add(candidates[i]);
  34.             dfs(i, add + candidates[i], target, li);
  35.             li.remove(li.size() - 1);
  36.         }
  37.     }
  38. }

LintCode 90：K数和II

https://www.lintcode.com/problem/k-sum-ii

描述

给定n个不同的正整数，整数k（1<= k <= n）以及一个目标数字。　　　　
在这n个数里面找出K个数，使得这K个数的和等于目标数字，你需要找出所有满足要求的方案。

样例

  1. 输入: [1,2,3,4], k = 2, target = 5
  2. 输出:  [[1,4],[2,3]]
  4. 输入: [1,3,4,6], k = 3, target = 8
  5. 输出:  [[1,3,4]]

解题思路

和上面的数字组合思路一样，只是个数有限

AC代码

  1. public class Solution {
  2.     List<List<Integer>> list = new ArrayList<>();
  3.     int[] a;
  5.     public List<List<Integer>> kSumII(int[] A, int k, int target) {
  6.         Arrays.sort(A);
  7.         a = A;
  8.         List<Integer> li = new ArrayList<>();
  10.         dfs(0, 0, 0, k, target, li);
  11.         return list;        
  12.     }
  14.     private void dfs(int index, int level, int add, int k, int target, List<Integer> li) {
  15.         if (add == target) {
  16.             if (level == k) {
  17.                 list.add(new ArrayList<>(li));
  18.             }
  19.             return;
  20.         }
  21.         if (level >= k || index == a.length) {
  22.             return;
  23.         }
  25.         for (int i = index; i < a.length; i++) {
  26.             if (add + a[i] > target) {
  27.                 break;
  28.             }
  29.             li.add(a[i]);
  30.             dfs(i + 1, level + 1, add + a[i], k, target, li);
  31.             li.remove(li.size() - 1);
  32.         }
  33.     }    
  34. }

LintCode 132：单词搜索II

https://www.lintcode.com/problem/word-search-ii

描述

给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。一个字母在一个单词中只能被使用一次。且字典中不存在重复单词

样例

  1. 输入：["doaf","agai","dcan"]，["dog","dad","dgdg","can","again"]
  2. 输出：["again","can","dad","dog"]
  3. 解释：
  4.   d o a f
  5.   a g a i
  6.   d c a n
  7. 矩阵中查找，返回 ["again","can","dad","dog"]。
  9. 输入：["a"]，["b"]
  10. 输出：[]
  11. 解释：
  12.  a
  13. 矩阵中查找，返回 []。

解题思路

从矩阵的每个点进行深搜。
优化：深搜到某一层时，如果这个前缀没在字典里出现过，其实就不用继续搜索。

  • 用哈希表存储前缀

  • 用字典树存储前缀

    AC代码

    1. public class Solution {
    3.   List<String> list;
    4.   // 哈希表存储前缀
    5.   Map<String, Boolean> prefixes;
    6.   int count = 0;
    7.   int[] a = {0, 0, 1, -1};
    8.   int[] b = {1, -1, 0, 0};
    9.   int n,m;
    10.   char[][] board;
    12.   public List<String> wordSearchII(char[][] board, List<String> words) {
    13.       if (board == null) return null;
    14.       if (board.length <1) return null;
    15.       if (board[0].length == 0) return null;
    16.       this.board = board;
    17.       list = new ArrayList<>();
    18.       prefixes = new HashMap<>();
    19.       count = 0;
    20.       // 存储前缀，value值为true代表这是一个单词
    21.       for (String str : words) {
    22.           for (int i = 1; i < str.length(); i++) {
    23.               String prefix = str.substring(0, i);
    24.               if (!prefixes.containsKey(prefix)) {
    25.                   prefixes.put(prefix, false);
    26.               }
    27.           }
    28.           prefixes.put(str, true);
    29.       }
    30.       n = board.length;
    31.       m = board[0].length;
    32.       boolean[][] flag = new boolean[n][m];
    33.       // 从每个点开始dfs
    34.       for (int i = 0; i < n; i++) {
    35.           for (int j = 0; j < m; j++) {
    36.               if (!prefixes.containsKey(board[i][j] + "")) {
    37.                   continue;
    38.               }
    39.               flag[i][j] = true;
    40.               dfs(flag, i,j,board[i][j]+"");
    41.               flag[i][j] = false;
    42.           }
    43.       }
    44.       return list;
    45.   }
    47.   public void dfs(boolean[][] flag, int x, int y, String s) {
    48.       if (prefixes.get(s)) {
    49.           // 去重
    50.           if (!list.contains(s)) {
    51.               list.add(s);
    52.           }
    53.       }
    54.       for (int i = 0; i < 4; i++) {
    55.           int x1 = x + a[i];
    56.           int y1 = y + b[i];
    57.           if (x1 < 0 || y1 < 0 || x1 >= n || y1 >= m || flag[x1][y1]) {
    58.               continue;
    59.           }
    60.           if (!prefixes.containsKey(s + board[x1][y1])) {
    61.               continue;
    62.           }
    63.           flag[x1][y1] = true;
    64.           dfs(flag, x1, y1, s + board[x1][y1]);
    65.           flag[x1][y1] = false;
    67.       }
    68.   }
    69. }