এই সমস্যায়, একটি স্ট্রিং দেওয়া থাকে এবং আমাদের স্ট্রিংয়ের সব সাবসিকোয়েন্স প্রিন্ট করতে হবে। সাবস্ট্রিংটি স্ট্রিংয়ের এলিমেন্ট ডিলিট করে তৈরি হয় কিন্তু অর্ডার একই থাকে (অর্থাৎ অর্ডার পরিবর্তন করা যাবে না)।
উদাহরণ দিয়ে বুঝি:
ইনপুট: xyz আউটপুট: 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
