牛客网刷题之字符串的全排列

怼烎@ 2023-07-03 06:12 25阅读 0赞

题目：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

## 输入描述: ##

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：

这道题和Leetcode活字印刷的那道题很相似，可以用一个visit来表示是否访问过，相同的字符且回退过了也是重复的

[https://blog.csdn.net/qq\_41901915/article/details/104131448][https_blog.csdn.net_qq_41901915_article_details_104131448]

代码：

import java.util.*;
    public class Solution {
        ArrayList<String> result=new ArrayList<>();
        public ArrayList<String> Permutation(String str) {
            if(str.length()<=0)
            {
                return result;
            }
            char[] target=str.toCharArray();
            Arrays.sort(target);
            StringBuilder track=new StringBuilder();
            boolean[] visit=new boolean[str.length()];
            backtrack(target,visit,track);
            return result;
        }
        public void backtrack(char[] target,boolean[] visit,StringBuilder track)
        {
            if(track.length()==target.length)
            {
                result.add(track.toString());
                return;
            }
            for(int i=0;i<target.length;i++)
            {
                //代码核心部分，如果访问过了，那么就跳过
                //访问过了，如果前面相同的字符已经回溯过了，那么就跳过
                if(visit[i]||(i>0&&target[i]==target[i-1]&&!visit[i-1]))
                {
                    continue;
                }
                track.append(target[i]);
                visit[i]=true;
                backtrack(target,visit,track);
                visit[i]=false;
                track.deleteCharAt(track.length()-1);
            }
        }
    }

[https_blog.csdn.net_qq_41901915_article_details_104131448]: https://blog.csdn.net/qq_41901915/article/details/104131448