题目链接

牛客网

题目描述

输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

回溯，需要记录哪个元素被访问过。
与Leetcode47类似

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
   
    public ArrayList<String> Permutation(String str) {
   
        ArrayList<String> res = new ArrayList<>();
        if (str==null || str.length()==0) return res;
        boolean[] marked = new boolean[str.length()];
        char[] ary = str.toCharArray();
        Arrays.sort(ary);
        backtracking(res, "", marked, ary);
        return res;
    }
    private void backtracking(ArrayList<String> res, String path, boolean[] marked, char[] ary) {
   
        if (path.length()==ary.length) {
   
            res.add(path);
            return;
        }
        for (int i=0;i<ary.length;i++) {
   
            if (i!=0 && ary[i]==ary[i-1] && !marked[i-1]) continue;
            if (marked[i]) continue;
            marked[i] = true;
            path = path+ary[i];
            backtracking(res, path, marked, ary);
            path = path.substring(0, path.length()-1);
            marked[i] = false;
        }
    } 
}