剑指 Offer 38. 字符串的排列

image.png

  1. class Solution {
  2.     List<String> res = new LinkedList();
  3.     boolean[] visited;
  4.     public String[] permutation(String s) {
  5.         if (s == null || s.length() == 0) return new String[0];
  6.         char[] chars = s.toCharArray();
  7.         Arrays.sort(chars);
  8.         visited = new boolean[chars.length];
  9.         backTrack(chars,new StringBuilder());
  10.         return res.toArray(new String[res.size()]);
  11.     }
  12.     private void backTrack(char[] chars, StringBuilder path) {
  13.         if (path.length() == chars.length) {
  14.             res.add(path.toString());
  15.             return;
  16.         }
  17.         for (int i = 0; i < chars.length; i++) {
  18.             if (visited[i]) continue;
  19.             if (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1]) continue;
  20.             visited[i] = true;
  21.             path.append(chars[i]);
  22.             backTrack(chars, path);
  23.             visited[i] = false;
  24.             path.deleteCharAt(path.length() - 1);
  25.         }
  26.     }
  27. }

78. 子集

image.png

  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> res = new LinkedList();
  4.         if (nums == null || nums.length == 0) return res;
  5.         List<Integer> path = new ArrayList();
  6.         res.add(path);
  7.         backTrack(nums, res, path, 0);
  8.         return res;
  9.     }
  10.     private void backTrack(int[] nums, List<List<Integer>> res, List<Integer> path , int start) {
  11.         res.add(new ArrayList(path));
  12.         for (int i = start; i < nums.length; i++) {
  13.             path.add(nums[i]);
  14.             backTrack(nums, res, path, i + 1);
  15.             path.remove(path.size() - 1);
  16.         }
  17.     }
  18. }

39. 组合总和

image.png

  1. class Solution {
  2.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  3.         List<List<Integer>> res = new LinkedList();
  4.         if (candidates == null || candidates.length == 0 || target < 1) return res;
  5.         List<Integer> path = new ArrayList();
  6.         backTrack(candidates, 0, target, res, path);
  7.         return res;
  8.     }
  9.     private void backTrack(int[] candidates, int start, int target, List<List<Integer>> res, List<Integer> path) {
  10.         if (target < 0) return;
  11.         if (target == 0) {
  12.             res.add(new ArrayList(path));
  13.             return;
  14.         }
  15.         for (int i = start; i < candidates.length; i++) {
  16.             path.add(candidates[i]);
  17.             backTrack(candidates, i, target - candidates[i], res, path);
  18.             path.remove(path.size() - 1);
  19.         }
  21.     }
  22. }

40. 组合总和 II

image.png

  1. class Solution {
  2.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  3.         List<List<Integer>> res = new LinkedList();
  4.         if (candidates == null || candidates.length < 1 || target < 1) return res;
  5.         Arrays.sort(candidates);
  6.         List<Integer> path = new ArrayList();
  7.         // boolean[] visited = new boolean[candidates.length];
  8.         backTrack(candidates, 0, target, path, res);
  9.         return res;
  10.     }
  11.     private void backTrack(int[] nums, int start, int target, List<Integer> path, List<List<Integer>> res) {
  12.         if (target < 0) return;
  13.         if (target == 0) {
  14.             res.add(new ArrayList(path));
  15.             return;
  16.         }
  17.         for (int i = start; i < nums.length; i++) {
  18.             if (i > start && nums[i] == nums[i - 1]) continue;
  19.             path.add(nums[i]);
  20.             backTrack(nums, i + 1, target - nums[i], path, res);
  21.             path.remove(path.size() - 1);
  22.         }
  23.     }
  24. }

46. 全排列

image.png

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList();
        if (nums == null || nums.length == 0) return res;
        List<Integer> path = new ArrayList();
        boolean[] visited = new boolean[nums.length];
        backTrack(nums, path, res, visited);
        return res;
    }
    private void backTrack(int[] nums, List<Integer> path, List<List<Integer>> res, boolean[] visited) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            path.add(nums[i]);
            visited[i] = true;
            backTrack(nums, path, res, visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

47. 全排列 II

image.png

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new LinkedList();
        if (nums == null || nums.length == 0) return res;
        List<Integer> path = new ArrayList();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        backTrack(nums, path, res, visited);
        return res;
    }
    private void backTrack(int[] nums, List<Integer> path, List<List<Integer>> res, boolean[] visited) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            path.add(nums[i]);
            visited[i] = true;
            backTrack(nums, path, res, visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

17. 电话号码的字母组合

image.png

class Solution {
    Map<Character,String> dict;
    public List<String> letterCombinations(String digits) {
        dict = new HashMap(){{
            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> res = new LinkedList();
        if (digits == null || digits.length() == 0) return res;
        StringBuilder path = new StringBuilder();
        backTracking(digits, 0, path, res);
        return res;
    }
    private void backTracking(String digits, int start, StringBuilder path, List<String> res) {
        if (start == digits.length()) {
            res.add(path.toString());
            return;
        }
        String letters = dict.get(digits.charAt(start));
        for (char c : letters.toCharArray()) {
            path.append(c);
            backTracking(digits, start + 1, path, res);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

将上面的map优化成数组

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