打印一个字符串的全部排列

打印一个字符串的全部排列

暴力递归 #

public static List<String> permutation1(String s) {
  List<String> ans = new ArrayList<>();
  if (s == null || s.length() == 0)
    return ans;
  char[] str = s.toCharArray();
  ArrayList<Character> rest = new ArrayList<Character>();
  for (char cha : str)
    rest.add(cha);

  String path = "";
  f(rest, path, ans);
  return ans;
}

private static void f(ArrayList<Character> rest, String path, List<String> ans) {
  if (rest.isEmpty())
    ans.add(path);
  else {
    int N = rest.size();
    for (int i = 0; i < N; i++) {
      char cur = rest.get(i);
      rest.remove(i);
      f(rest, path + cur, ans);
      rest.add(i, cur);
    }
  }
}

暴力递归优化 #

public static List<String> permutation2(String s) {
  List<String> ans = new ArrayList<>();
  if (s == null || s.length() == 0)
    return ans;
  char[] str = s.toCharArray();
  g(str, 0, ans);
  return ans;

}

private static void g(char[] str, int index, List<String> ans) {
  if (index == str.length) {
    ans.add(String.valueOf(str));
  } else {
    for (int i = index; i < str.length; i++) {
      swap(str, index, i);
      g(str, index + 1, ans);
      swap(str, i, index);// 恢复现场
    }
  }
}

暴力递归，去重 #

使用数组记录出现过的 ASCII 码，达到去重的效果

private static void g2(char[] str, int index, List<String> ans) {
  if (index == str.length) {
    ans.add(String.valueOf(str));
  } else {
    boolean[] visited = new boolean[256];// 去重数组 记录是否出现过
    for (int i = index; i < str.length; i++) {
      if (!visited[str[i]]) { // 去重操作
        visited[str[i]] = true;
        swap(str, index, i);
        g2(str, index + 1, ans);
        swap(str, i, index);// 恢复现场
      }
    }
  }
}