输出字符串的全部排列--java实现

青旅半醒 2022-10-09 00:45 172阅读 0赞

今天和大家分享一道算法题，输出字符串的全部排列；

比如 传 ab 字符串，打印结果应该为：ab、ba

实现思想：采用递归加动态规划的思路，加上恢复现场的原理，同时解决。这里提供两个解决方案和一个去重的解决方案，供大家参考！

1、删除元素的方案，核心代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author wanghuainan
     * @date 2021/6/22 11:22
     */
    public class NanDaoPrintAllPermutations {
    
        public static void main(String[] args) {
            String s = "abc";
            List<String> list1 = test1(s);
            for(String str : list1){
                System.out.println(str);
            }
         
            System.out.println();
        }
    
    
        /**
         * 删除字符的方案
         * @param str
         * @return
         */
        private static List<String> test1(String str) {
            List<String> list = new ArrayList<>();
            if(str == null || str.length() == 0){
                return list;
            }
            char[] chars = str.toCharArray();
            ArrayList<Character> rest = new ArrayList<>();
            for(char c : chars){
                rest.add(c);
            }
            String path = "";
            t1(rest,path,list);
            return list;
        }
    
        private static void t1(ArrayList<Character> rest, String path, List<String> list) {
            if(rest.isEmpty()){//为空时，即所有元素均加入path后，添加到list
                list.add(path);
            }else {
                int n = rest.size();
                for(int i = 0;i < n;i++){
                    char cur = rest.get(i);//获取此节点数据
                    rest.remove(i);//获取此处数据后暂时删除此节点
                    t1(rest,path + cur,list);
                    rest.add(i,cur);//恢复现场
                }
            }
        }
    
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

2、替换元素位置的方案，核心代码：

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author wanghuainan
     * @date 2021/6/22 11:22
     */
    public class NanDaoPrintAllPermutations {
    
        public static void main(String[] args) {
            String s = "abc";
             List<String> list2 = test2(s);
            for(String str : list2){
                System.out.println(str);
            } 
            System.out.println();
        }
    
        /**
         * 替换位置的方案
         * @param str
         * @return
         */
        private static List<String> test2(String str) {
            List<String> list = new ArrayList<>();
            if(str.length() == 0 || str == null){
                return list;
            }
            char[] chars = str.toCharArray();
            t2(chars,0,list);
            return list;
        }
     
        private static void t2(char[] str, int index, List<String> list) {
            if(index == str.length){
                list.add(String.valueOf(str));
            }else {
                for (int i = index;i < str.length;i++){
                    swap(str,index,i);//交换位置
                    t2(str,index + 1,list);//遍历添加
                    swap(str,index,i);//恢复现场
                }
            }
        }
    
        private static void swap(char[] str, int index, int i) {
            char temp = str[i];
            str[i] = str[index];
            str[index] = temp;
        }
     
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

3、获得去重的全排列，采用布尔类型的标识（也可以用set集合过滤，只是效率差一些），核心代码：

import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author wanghuainan
     * @date 2021/6/22 11:22
     */
    public class NanDaoPrintAllPermutations {
    
        public static void main(String[] args) {
            String s = "acc";
    
            List<String> list3 = test3(s);
            for(String str : list3){
                System.out.println(str);
            }
            System.out.println();
        }
    
       
        /**
         * 去重的全排列
         * @param str
         * @return
         */
        private static List<String> test3(String str) {
            List<String> list = new ArrayList<>();
            if(str.length() == 0 || str == null){
                return list;
            }
            char[] chars = str.toCharArray();
            t3(chars,0,list);
            return list;
        }
    
        private static void t3(char[] str, int index, List<String> list) {
            if(index == str.length){
                list.add(String.valueOf(str));
            }else {
                boolean[] flag = new boolean[256];
                for (int i = index;i < str.length;i++){
                    if(!flag[str[i]]){
                        flag[str[i]] = true;
                        swap(str,index,i);//交换位置
                        t3(str,index + 1,list);//遍历添加
                        swap(str,index,i);//恢复现场
                    }
                }
            }
        }
    
        private static void swap(char[] str, int index, int i) {
            char temp = str[i];
            str[i] = str[index];
            str[index] = temp;
        }
    
    }

执行结果：

![2021062220274589.png][]

到此，三种解决方案分享完毕，递归和动态规划是算法领域比较难以理解的内容，大家要多思考，多联系，定会很快理解掌握。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/b6d6ef4c17f942d6be0a9b79227107fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221005/90ca4712e915486cbbc3d0b5b9e70f2a.png
[2021062220274589.png]: /images/20221005/65788f397e034671b98efd83b2e2868b.png