美文网首页
41_字符串的排列

41_字符串的排列

作者: 是新来的啊强呀 | 来源:发表于2020-06-06 00:11 被阅读0次

    要求:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
    思路:使用全排列算法
    方法见19_全排列递归算法

    public class L39_permutation {
        // 全排列算法
        static ArrayList<String> res = new ArrayList<>();
        static char[] c;
        public static String[] permutation(String str) {
            // 将字符串转化为数组
            c = str.toCharArray();
            int len = c.length;
            dfs(0,len);
            // 将ArrayList转化为字符数组,先把链表的每个值取出来,然后拼接到一起,隔着",",利用字符分割split(",")切分成数组
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<=res.size()-1;i++){
                sb.append(res.get(i)+",");
            }
            String[] val = sb.deleteCharAt(sb.length()-1).toString().split(",");
            return val;
        }
        //递归
        public static void dfs(int m, int len){
            HashSet<Character> set = new HashSet<>();
            if(m == len){
                res.add(String.copyValueOf(c));
            }else{
                for(int i=m; i<len;i++){
                    // 如果有重复的字符,要剪掉,即相同的字母只固定一次
                    if(set.contains(c[i])) continue; // 重复,因此剪枝
                    set.add(c[i]);
                    // 交换,固定第一位
                    char temp = c[m];
                    c[m] = c[i];
                    c[i] = temp;
                    // 递归
                    dfs(m+1, len);
                    // 交换回去
                    temp = c[m];
                    c[m] = c[i];
                    c[i] = temp;
                }
            }
        }
    
        public static void main(String[] args) {
            String[] str = permutation("abbb");
            int len = str.length;
            for(int i=0; i<len;i++){
                System.out.println(str[i]);
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:41_字符串的排列

          本文链接:https://www.haomeiwen.com/subject/xrrzzhtx.html