【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 + " ");
        }
    }
}