พิมพ์ Subsequences ทั้งหมดของสตริงใน C++

ในปัญหานี้ เราจะได้รับสตริง และต้องพิมพ์ subsequences ทั้งหมดของสตริง Substring ที่สร้างขึ้นมาจากการลบองค์ประกอบของสตริง แต่ลำดับจะคงเดิม (คือ ไม่สามารถเปลี่ยนลำดับได้)

ตัวอย่างเพื่อความเข้าใจ

Input: xyz
Output: x, y, z, xy, yz, xz, xyz

คำอธิบาย - ในตัวอย่างข้างต้น เราเห็นว่ามีแค่ตัวอักษรที่ถูกลบเพื่อสร้าง substring ไม่มีการจัดเรียงใหม่เกิดขึ้น

สามารถมีหลายวิธีในการแก้ปัญหานี้ ที่นี่เราจะอธิบายหลายวิธีเพื่อให้เข้าใจวิธีการ

วิธีหนึ่งคือการเลือกองค์ประกอบของสตริงและกำจัดบางส่วนเพื่อสร้างลำดับ ในวิธีนี้ เราจะเลือกองค์ประกอบบางส่วนและลบส่วนที่เหลือเพื่อสร้าง substring

โปรแกรมตัวอย่าง (วิธีที่ 1 - Java)

import java.util.*;
class Main {
    public static ArrayList<String> subStringSeq = new ArrayList<String>();
    public static void main(String[] args) {
        String s = "pqrs";
        System.out.println("All the substring found are :");
        findSubString(s, "");
        System.out.println(subStringSeq);
    }
    public static void findSubString(String s, String ans) {
        if (s.length() == 0) {
            subStringSeq.add(ans);
            return;
        }
        findSubString(s.substring(1), ans + s.charAt(0));
        findSubString(s.substring(1), ans);
    }
}

ผลลัพธ์

All the substring found are -

[pqrs, pqr, pqs, pq, prs, pr, ps, p, qrs, qr, qs, q, rs, r, s, ]

วิธีอื่น คือการวนลูปผ่านสตริงและสร้าง substring และลบตัวอักษรของลำดับเพื่อสร้าง substrings ที่นี่เราจะใช้ list เก็บ substrings และตรวจสอบว่าลำดับที่พบซ้ำหรือไม่

โปรแกรมตัวอย่าง (วิธีที่ 2 - Java)

import java.util.HashSet;
public class Main {
    static HashSet<String> subString = new HashSet<>();
    static void findSubString(String str) {
        for (int i = 0; i < str.length(); i++) {
            for (int j = str.length(); j > i; j--) {
                String sub_str = str.substring(i, j);
                if (!subString.contains(sub_str))
                    subString.add(sub_str);
                for (int k = 1; k < sub_str.length() - 1; k++) {
                    StringBuffer sb = new StringBuffer(sub_str);
                    sb.deleteCharAt(k);
                    if (!subString.contains(sb));
                        findSubString(sb.toString());
                }
            }
        }
    }
    public static void main(String[] args) {
        String s = "pqrs";
        System.out.println("The subsequence is ");
        findSubString(s);
        System.out.println(subString);
    }
}

ผลลัพธ์

The subsequence is

[rs, pq, qr, pr, qs, ps, prs, p, pqr, q, r, s, pqs, qrs, pqrs]

อีกวิธีหนึ่งคือการกำหนดตัวอักษรและหา substring ในวิธีนี้ เราจะกำหนดองค์ประกอบของสตริงทีละตัว และใช้ตัวอักษรที่กำหนดเหล่านี้หา subsequence การเรียกซ้ำของวิธีนี้จะสร้าง string subsequence ที่ต้องการ

โปรแกรมตัวอย่าง (วิธีที่ 3 - Java)

class Main {
    static void subString(String str, int n, int index, String curr) {
        if (index == n) {
            return;
        }
        System.out.print(curr + ", ");
        for (int i = index + 1; i < n; i++) {
            curr += str.charAt(i);
            subString(str, n, i, curr);
            curr = curr.substring(0, curr.length() - 1);
        }
    }
    static void printSubStrings(String str) {
        int index = -1;
        String curr = "";
        subString(str, str.length(), index, curr);
    }
    public static void main(String[] args) {
        String str = "pqrs";
        System.out.println("The subStrings are :");
        printSubStrings(str);
    }
}

ผลลัพธ์

The subStrings are -

p, pq, pqr, pqrs, pqs, pr, prs, ps, q, qr, qrs, qs, r, rs, s