พิมพ์ลำดับย่อยทั้งหมดของสตริงใน C++

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

มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า −

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

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

อาจมีวิธีแก้ปัญหานี้ได้หลายวิธี เราจะพูดคุยกันสองสามวิธีเพื่อทำความเข้าใจวิธีการ

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

ตัวอย่าง

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);
   }
}

ผลลัพธ์

สตริงย่อยทั้งหมดที่พบคือ −

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

วิธีอื่น อาจวนซ้ำสตริงและสร้างสตริงย่อย และวางอักขระของซีเควนซ์เพื่อสร้างสตริงย่อย ที่นี่ เราจะใช้รายการเพื่อจัดเก็บสตริงย่อย และตรวจสอบว่าได้ลำดับที่พบแล้วหรือไม่

ตัวอย่าง

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);
   }
}

ผลลัพธ์

รองลงมาคือ

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

อีกวิธีหนึ่งสามารถแก้ไขอักขระและค้นหาสตริงย่อยได้ ในวิธีนี้ เราจะแก้ไของค์ประกอบของสตริงทีละรายการและใช้อักขระคงที่เหล่านี้ เราจะพบส่วนย่อย การเรียกซ้ำของเมธอดนี้จะสร้างลำดับย่อยของสตริงที่จำเป็น

ตัวอย่าง

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);
   }
}

ผลลัพธ์

สตริงย่อยคือ −

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