【LeeCode】字符串的全排列

【题目描述】

输入字符串str， 返回str的字符的全排序

【示例】

输入：qwe

输出：qwe qew ewq eqw wqe weq

注意： 如果输入的是n个相同的字符，那么也就只有1种排列组合

【代码】

list: 保留最后的结果，且初始字符为str的第一个字母

new_list： 保留中间结果, 且每次把新的字符加到原字符的左右, 然后利用

                 substring进行字符拼接

package com.company;

import java.util.*;

/**
 * 2022-06-18
 */
public class Test {
    public static void main(String[] arg) {
        String str = "aaaa";
        quanpai(str);
    }

    private static void quanpai(String str) {
        if (str.length() == 0) {
            return;
        }else if(str.length() == 1){
            System.out.println("共计: " + 1);
            return;
        }
        // 如果输入的都是n个相同字符串，那么也就1种排列组合,这里不考虑这个场景

        List<String> list = new ArrayList<>();
        // 添加首字母
        list.add(str.charAt(0) + "");
        // 外层循环负责获取每次的字符
        for (int i = 1; i < str.length(); i++) {
            List<String> new_list = new ArrayList<>();
            // 获取第二个字符
            char ch = str.charAt(i);
            for (String s : list) {
                // 第二个字符只有2个选择，放在第一个的前面或者后面
                new_list.add(s + ch);
                new_list.add(ch + s);
                // 注意这里从1开始，因为0就是起始值且subString(0,j)
                for (int j = 1; j < s.length(); j++) {
                    String tmp = s.substring(0, j) + ch + s.substring(j);
                    new_list.add(tmp);
                }
            }
            list = new_list;
        }
        System.out.println("共计: " + list.size());

        for (String ss : list) {
            System.out.print(ss + " ");
        }
    }
}

典型Leecode： ​​https://leetcode.cn/problems/permutation-in-string/​​