字符串的排列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        boolean[] visited = new   boolean[chars.length];
        dfs(chars, res, new StringBuilder(),  visited);
        return res;
    }
    void dfs(char[] chars, ArrayList<String> res, StringBuilder tmp,
             boolean[] visited) {
        if (chars.length == tmp.length()) {
            res.add(new String(tmp));
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1]) {
                continue;
            }
            tmp.append(chars[i]);
            visited[i] = true;
            dfs(chars, res, tmp,  visited);
            visited[i] = false;
            tmp.deleteCharAt(tmp.length() - 1);
        }
    }
}

含重复项的全排列

import java.util.*;

public class Solution {
    private ArrayList<String> res = new ArrayList<>(); // 结果集合
    private StringBuilder path = new StringBuilder(); // 一次路径
    private boolean[] visited; // 访问标记

    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] s = str.toCharArray();
        Arrays.sort(s);  // 排序(防重复要用到)
        visited = new boolean[s.length];

        backtrack(s, 0); // 调用

        return res;
    }

    // 回溯
    private void backtrack(char[] s, int k) {
        if (k == s.length) { // 递归出口
            res.add(path.toString());
            return;
        }

        for (int i = 0; i < s.length; i++) {
            if (visited[i] || i > 0 && s[i] == s[i - 1] && !visited[i - 1])
                continue; // 已访问||同字符保证依序访问(防重复)
            path.append(s[i]); //选择
            visited[i] = true;
            backtrack(s, k + 1); // 下一层
            visited[i] = false;
            path.deleteCharAt(path.length() - 1); // 撤销选择
        }
    }
}

1. Java递归回溯。但有几个注意点
   • str（这里是对应的Char Array）要先排序。确保重复的位置会出现在相邻的位置；
   • 整个过程中，排完序后的原始str就不会再变了。结果的收集与回溯时现场恢复使用的是StringBuiler进行记录；

import java.util.*;


public class Solution {
    public ArrayList<String> Permutation (String str) {
        char[] strArray = str.toCharArray();
        boolean[] visited = new boolean[strArray.length];
        ArrayList<String> ans = new ArrayList<>();
        StringBuilder path = new StringBuilder();

        Arrays.sort(strArray);
        backtrace(0, strArray, visited, ans, path);
        return ans;
    }

    private void backtrace(int start, char[] strArray, boolean[] visited,
                            ArrayList<String> ans, StringBuilder path) {
        if (start == strArray.length) {
            ans.add(path.toString());
            return;
        }

        for (int i = 0; i < strArray.length; i++) {
            if (visited[i] || (i > 0 && strArray[i-1] == strArray[i] && !visited[i-1])) {
                continue;
            }
            visited[i] = true;
            path.append(strArray[i]);
            backtrace(start+1, strArray, visited, ans, path);
            visited[i] = false;
            path.delete(path.length()-1, path.length());
        }
    }
}

2. Java手动实现nextPermutation()函数

import java.util.*;


public class Solution {
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> ans = new ArrayList<>();

        char[] strArray = str.toCharArray();
        Arrays.sort(strArray);
        do {
            ans.add(new String(strArray));
        } while (nextPermutation(strArray));

        return ans;
    }

    private boolean nextPermutation(char[] strArray) {
        if (strArray.length <= 1) return false;

        int i = strArray.length-1;
        while (i > 0 && strArray[i-1] >= strArray[i]) i -= 1;
        if (i > 0) {
            int j = strArray.length-1;
            while (strArray[i-1] >= strArray[j]) j -= 1;
            swap(strArray, i-1, j);
        }

        reverse(strArray, i, strArray.length-1);
        return i > 0;
    }

    private void swap(char[] strArray, int left, int right) {
        char temp = strArray[left];
        strArray[left] = strArray[right];
        strArray[right] = temp;
    }

    private void reverse(char[] strArray, int left, int right) {
        while (left < right) {
            swap(strArray, left, right);
            left += 1;
            right -= 1;
        }
    }
}

3. 总结：

• 上述两种方法，无论是哪一种方法，为了不重不漏，都必须在最开始将String按照字典序非降序排列好；
• 上述两种方法不仅对String的排列可行。将String替换为int[]也是可以的，即对应之前的全排列题目；

public ArrayList<String> Permutation (String str) {
        HashSet<String> set = new HashSet<>();
        p(str.toCharArray(),0,set);
        return new ArrayList<String>(set);
    }

    public void p(char[] str,int start,HashSet<String> set){
        if(start == str.length) set.add(new String(str));
        for(int i=start;i<str.length;i++){
            if(i>start && str[start] == str[i]) continue;
            swap(str,start,i);
            p(str,start+1,set);
            swap(str,start,i);
        }
    }

    public void swap(char[] str,int i,int j){
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        char[] chs = str.toCharArray();
        backTrack(chs);
        return res;
    }

    ArrayList<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    HashSet<Integer> used = new HashSet<>(); // 记录每个path（纵向）使用过的字符索引 
    private void backTrack(char[] chs) {
        if (path.length() == chs.length) {
            res.add(path.toString());
            return;
        }

        HashSet<Character> usedRow = new HashSet<>();  // 记录每层使用过的字符
        for (int i = 0; i < chs.length; i++) {
            if (used.contains(i) || usedRow.contains(chs[i])) continue;
            path.append(chs[i]);
            used.add(i);
            usedRow.add(chs[i]);
            backTrack(chs);
            path.delete(path.length() - 1, path.length());
            used.remove(i);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        // 左程云老师讲过全排列的分支限界递归法解决不重复全排列问题
        // 调用一个递归函数，这个递归函数负责对当前i位置的字符进行与i ~ chars.length - 1中的位置依次互换，然后继续考察i + 1处的情况
        // 分支界限法去重：定义一个HashSet，这个位置没有出现过该值才允许进入分支，否则跳过

        // 算法的时间复杂度0(N!)，额外空间复杂度0(N!)

        // 用于记录所有路径的结果
        ArrayList<String> finalResults = new ArrayList<>();

        // 调用这个递归函数，从num数组的0位置开始，将每一次找到的oneResult填进finalResult中
        process(str.toCharArray(), finalResults, 0);

        // 返回最终的答案finalResults
        return finalResults;
    }

    public void process(char[] chars, ArrayList<String> finalResults, int i) {
        // 递归出口（底部）
        if (i == chars.length) {
            // i越界了，说明整个数组遍历完毕了，将单个路径上的答案oneResult写入总答案finalResults中
            finalResults.add(String.valueOf(chars));
        }

        // 递归分支
        HashSet<Character> set = new HashSet<>();
        for (int j = i; j < chars.length; j++) {
            if (!set.contains(chars[j])) {
                // 将num[j]登记
                set.add(chars[j]);
                // 假设本位置与j位置的元素交换
                swap(chars, i, j);
                // 在交换完的基础上继续考察num数组中i+1往后的位置该如何排列
                process(chars, finalResults, i + 1);
                // 注意！恢复现场，继续尝试将本位值与num[j + 1]位置的元素交换
                // 踩坑点2：一定要【恢复现场】，要不然无法准确列出要分支的情况
                swap(chars, j, i);
            }
        }
    }

    // 数组元素交换函数
    public void swap(char[] chars, int i, int j) {
        if (i == j) {
            return;
        }
        char t = chars[i];
        chars[i] = chars[j];
        chars[j] = t;
    }
}

HashSet<String> res=new HashSet<>();

public ArrayList<String> Permutation (String str) {
    // write code here
    dfs(str.toCharArray() ,new boolean[str.length()] ,new StringBuilder());
    return new ArrayList<String>(res);
}

public void dfs(char[] cs ,boolean[] flag ,StringBuilder sb){
    if(sb.length()==cs.length){
        res.add(sb.toString());
        return;
    }
    for(int i=0;i<cs.length;i++){
        if(flag[i]){
            continue;
        }
        flag[i]=true;
        sb.append(cs[i]);
        dfs(cs ,flag ,sb);
        sb.deleteCharAt(sb.length()-1);
        flag[i]=false;
    }
}

/*
全排列版本
*/
public class Solution {
    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        str = new String(charArray);
        ArrayList<String> res = new ArrayList<>();
        String list = "";
        boolean[] visit = new boolean[str.length()];
        dfs(str,res,list,visit);
        return res;

    }
    private void dfs(String str,ArrayList<String> res,String list,boolean[] visit){
        if(str.length() == list.length()){
            res.add(list);
            return;
        }

        for(int i =0;i<str.length();i++){
            if(visit[i] || i>0&&str.charAt(i)==str.charAt(i-1) && visit[i-1]){
                continue;
            }
            visit[i] = true;
            list += str.charAt(i);
            dfs(str,res,list,visit);
            list = list.replaceAll(".$","");
            visit[i] = false;
        }
    }
}

public ArrayList<String> Permutation (String str) {
        // 全排列
        //String变char[]
        char[] charrr=str.toCharArray();//String变char[]:str.toCharArray()
        //排序（去重必然排序
        Arrays.sort(charrr);
        boolean[] used=new boolean[str.length()];
        ArrayList<String> ans=new ArrayList<>();
        ArrayList<Character> list=new ArrayList<>();//作为path
        build(charrr,used,ans,list);
        return ans;
    }
    public void build(char[] charrr,boolean[] used,ArrayList<String> ans,ArrayList<Character> list){
        //截至条件:list.size()==char.length
        //把char拼接到String上 用StringBuilder
        if(list.size()==charrr.length){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<list.size();i++){
                sb.append(list.get(i));
            }
            ans.add(sb.toString());  //把StringBuilder变成String,  sb.toString()
            return;
        }
        for(int i=0;i<charrr.length;i++){
            //剪枝
            //被用过是true
            if(used[i]==true) continue;
            if(i>0&&charrr[i]==charrr[i-1]&&used[i-1]==true) continue;
            list.add(charrr[i]);
            used[i]=true;
            build(charrr,used,ans,list);
            list.remove(list.size()-1);
            used[i]=false;
        }

    }

public class Solution {
    public ArrayList<String> Permutation(String str) {
        // 将字符串转为字符数组
        char[] sArray = str.toCharArray();
        // 排序，为了后面对树层去重
        Arrays.sort(sArray);
        // 路径
        LinkedList<Character> track = new LinkedList<>();
        // 结果集
        ArrayList<String> ans = new ArrayList<>();
        // 辅助树枝去重和树层去重
        boolean[] used = new boolean[sArray.length];
        backTrack(sArray, track, ans, used);
        return ans;
    }
    private void backTrack(char[] sArray, LinkedList<Character> track,
                           ArrayList<String> ans, boolean[] used) {
        //收获结果
        if (sArray.length == track.size()) {
            ans.add(parseToString(track));
            return;
        }
        for (int i = 0; i < sArray.length; i++) {
            // 同一个树枝上一个数不可以出现两次
            if (used[i]) {
                continue;
            }
            // 同一层不能选择同一个数
            if (i > 0 && sArray[i] == sArray[i - 1] && !used[i - 1]) {
                continue;
            }
            // 标记本次选择
            used[i] = true;
            // 做出选择
            track.addLast(sArray[i]);
            backTrack(sArray, track, ans, used);
            // 撤销标记本次选择
            used[i] = false;
            // 撤销选择
            track.removeLast();
        }
    }
    private String parseToString(LinkedList<Character> track) {
        // 将track转变为字符串返回
        StringBuilder ans = new StringBuilder();
        for (Character c : track) {
            ans.append(c);
        }
        return ans.toString();
    }
}

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        if (Objects.isNull(str) || str.isEmpty()) return new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        generatStr(str, 0, set);
        return new ArrayList(set);
    }

    private void generatStr(String str, int i, HashSet<String> set) {
        char[] chars = str.toCharArray();
        // 第i位置的字符与str后面每个位置换一遍
        for (int i1 = i; i1 < chars.length; i1++) {
            char temp = chars[i];
            chars[i] = chars[i1];
            chars[i1] = temp;
            set.add(String.valueOf(chars));
            // 得到的新字符串，再接着与后面的交换(如题目画的图那样)
            generatStr(String.valueOf(chars), i + 1, set);
        }
    }
}

import java.util.*;

public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> res = new ArrayList<>();
        char[] chars = str.toCharArray();
        Permutation(chars, res, 0);

        return res;
    }
    public void Permutation(char[] chars, ArrayList<String> res, int i) {
        if(i == chars.length){
            res.add(new String(chars));
            return;
        }
        // 每一层都使用一个hashset 来保存没有重复的字符，如果有重复，则不递归尝试获取排列
        HashSet<Character> temp = new HashSet<>();
        // 每个j位置的数都有机会来到i位置
        for (int j = i; j < chars.length; j++) {
            // 只要set中不包含j索引的字符，那么递归求解
            if(!temp.contains(chars[j])){
                // 添加记录
                temp.add(chars[j]);
                // 交换位置
                permutationSwap(chars, i, j);
                // 递归求解
                Permutation(chars, res, i+1);
                // 交换回来，下次循环继续
                permutationSwap(chars, i, j);
            }
        }
    }
    public void permutationSwap(char[] chars, int i, int j){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}