พิมพ์การเรียงสลับทั้งหมดของสตริงด้วย ArrayList ใน Java

ในปัญหานี้ เราได้รับสตริงขนาด n และต้องพิมพ์การเรียงสลับ (permutation) ทั้งหมดของสตริง โดยใช้ ArrayList

ตัวอย่าง

Input: string = 'XYZ'
Output: XYZ, XZY, YXZ, YZX, ZXY, ZYX

วิธีแก้ปัญหา

เราจะสร้างการเรียงสลับทั้งหมดของตัวอักษรในสตริง โดยใช้ฟังก์ชัน recursive ที่คืนค่า ArrayList

การนำไปใช้ด้วย ArrayList

import java.util.ArrayList;

public class Main {
    static void printArrayList(ArrayList<String> combo) {
        combo.remove("");
        for (int i = 0; i < combo.size(); i++)
            System.out.print(combo.get(i) + "\t");
    }

    public static ArrayList<String> generatePermutation(String str) {
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        char ch = str.charAt(0);
        String subStr = str.substring(1);
        ArrayList<String> lastCombination = generatePermutation(subStr);
        ArrayList<String> newCombination = new ArrayList<>();
        for (String val : lastCombination) {
            for (int i = 0; i <= val.length(); i++) {
                newCombination.add(val.substring(0, i) + ch + val.substring(i));
            }
        }
        return newCombination;
    }

    public static void main(String[] args) {
        String str = "NOPQ";
        System.out.println("Permutations of string are:");
        printArrayList(generatePermutation(str));
    }
}

ผลลัพธ์

Permutations of string are:
NOPQ ONPQ OPNQ OPQN NPOQ PNOQ PONQ POQN NPQO PNQO PQNO PQON NOQP ONQP OQNP OQPN NQOP QNOP QONP QOPN NQPO QNPO QPNO QPON

อธิบายโค้ด

• generatePermutation() เป็นฟังก์ชัน recursive ที่สร้างการเรียงสลับ
• กรณีฐาน (base case): สตริงว่าง คืนค่า ArrayList ที่มีสตริงว่างเดียว
• ขั้นตอน recursive: นำตัวอักษรแรกไปแทรกที่ทุกตำแหน่งของการเรียงสลับของสตริงย่อย
• printArrayList() พิมพ์ผลลัพธ์ โดยลบสตริงว่างออกก่อน

ความซับซ้อน

• เวลา: O(n × n!) - มี n! การเรียงสลับ แต่ละอันยาว n
• พื้นที่: O(n × n!) - เก็บการเรียงสลับทั้งหมด