Given a string with possible duplicate characters, return a list with all permutations of the characters.

Examples

• Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]
• Set = "aba", all permutations are ["aab", "aba", "baa"]
• Set = "", all permutations are [""]
• Set = null, all permutations are []

Solution 1:

先排序。每次recursion从头扫，用一个boolean[] visited记录已经访问过的，string[i] == string[i - 1] && !visited[i]说明上一个相同的字母在该层recursion已用过，这两种情况都continue。(没有duplicate的话，只需!visited[i])

 public List<String> permutations(String set) {
    // Write your solution here.
    if (set == null) {
      return new ArrayList<String>();
    }
    List<String> result = new ArrayList<>();
    boolean[] visited = new boolean[set.length()];
    char[] chars = set.toCharArray();
    Arrays.sort(chars);
    helper(chars, new StringBuilder(), result, visited);
    return result;
  }

  private void helper(char[] set, StringBuilder path, List<String> result, boolean[] visited) {
    if (path.length() == set.length) {
      result.add(path.toString());
      return;
    }
    for (int i = 0; i < set.length; i++) {
      char c = set[i];
      //不能只用hashset记录用过的字母或者index
      if (visited[i] || i > 0 && c == set[i - 1] && !visited[i - 1]) {
        continue;
      }
      path.append(c);
      visited[i] = true;
      helper(set, path, result, visited);
      visited[i] = false;
      path.deleteCharAt(path.length() - 1);
    }
  }

Solution 2:

不用排序。每次recursion从index开始扫，每层都要新建hashset记录该层用过的字母，把index和i的字母swap. (没有duplicate的话，不需hashset)

  public List<String> permutations(String set) {
    // Write your solution here.
    if (set == null) {
      return new ArrayList<String>();
    }
    List<String> result = new ArrayList<>();
    char[] chars = set.toCharArray();
    helper2(chars, 0, result);
    return result;
  }

  private void helper2(char[] set, int index, List<String> result) {
    if (index == set.length) {
      result.add(new String(set));
      return;
    }
    Set<Character> hashset = new HashSet<>();
    for (int i = index; i < set.length; i++) {
      if (!hashset.contains(set[i])) {
        swap(set, index, i);
        helper2(set, index + 1, result);
        swap(set, index, i);
        hashset.add(set[i]);
      }
    }
  }

  private void swap(char[] set, int index, int i) {
    char temp = set[index];
    set[index] = set[i];
    set[i] = temp;
  }