इस समस्या में, हमें एक स्ट्रिंग दी गई है और हमें स्ट्रिंग के सभी उपअनुक्रम प्रिंट करने हैं। उत्पन्न उपस्ट्रिंग स्ट्रिंग के तत्वों को हटाकर बनाई जाती है लेकिन क्रम वही रहता है (अर्थात क्रम बदला नहीं जा सकता)।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट: 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
