इस लेख में, हम समझेंगे कि स्ट्रिंग के सभी सबसेट्स कैसे खोजें। String एक डेटा प्रकार है जिसमें एक या अधिक कैरेक्टर्स होते हैं और यह डबल कोट्स (" ") में संलग्न होता है। स्ट्रिंग का एक भाग या उपसमूह सबस्ट्रिंग कहलाता है।
नीचे इसका प्रदर्शन है:
मान लीजिए हमारा इनपुट है:
स्ट्रिंग परिभाषित है: JVM
वांछित आउटपुट होगा:
स्ट्रिंग के सबसेट्स हैं: J JV JVM V VM M
एल्गोरिदम
चरण 1 - शुरू चरण 2 - घोषित करें चरण 3 - मान परिभाषित करें चरण 4 - हर इटरेशन के बाद बढ़ने के लिए एक अस्थायी वेरिएबल इनिशियलाइज़ करें चरण 5 - दो नेस्टेड लूप्स का उपयोग करके स्ट्रिंग की लंबाई के माध्यम से इटरेट करें चरण 6 - दी गई रेंज के बीच सबस्ट्रिंग खोजें, और हर इटरेशन के बाद अस्थायी वेरिएबल बढ़ाएं चरण 7 - लूप का उपयोग करके सबस्ट्रिंग्स प्रदर्शित करें चरण 8 - रुकें
उदाहरण 1
यहाँ, हम सभी ऑपरेशन्स को 'main' फंक्शन के तहत बांधते हैं।
public class Demo {
public static void main(String[] args) {
String input_string = "JVM";
int string_length = input_string.length();
int temp = 0;
System.out.println("स्ट्रिंग परिभाषित है: " + input_string);
String string_array[] = new String[string_length * (string_length + 1) / 2];
for (int i = 0; i < string_length; i++) {
for (int j = i; j < string_length; j++) {
string_array[temp] = input_string.substring(i, j + 1);
temp++;
}
}
System.out.println("स्ट्रिंग के सबसेट्स हैं: ");
for (int i = 0; i < string_array.length; i++) {
System.out.println(string_array[i]);
}
}
}
आउटपुट
स्ट्रिंग परिभाषित है: JVM स्ट्रिंग के सबसेट्स हैं: J JV JVM V VM M
उदाहरण 2
यहाँ, हम ऑपरेशन्स को फंक्शन्स में एनकैप्सुलेट करते हैं जो ऑब्जेक्ट-ओरिएंटेड प्रोग्रामिंग प्रदर्शित करते हैं।
public class Demo {
static void subsets(String input_string) {
int string_length = input_string.length();
int temp = 0;
String string_array[] = new String[string_length * (string_length + 1) / 2];
for (int i = 0; i < string_length; i++) {
for (int j = i; j < string_length; j++) {
string_array[temp] = input_string.substring(i, j + 1);
temp++;
}
}
System.out.println("स्ट्रिंग के सबसेट्स हैं: ");
for (int i = 0; i < string_array.length; i++) {
System.out.println(string_array[i]);
}
}
public static void main(String[] args) {
String input_string = "JVM";
System.out.println("स्ट्रिंग परिभाषित है: " + input_string);
subsets(input_string);
}
}
आउटपुट
स्ट्रिंग परिभाषित है: JVM स्ट्रिंग के सबसेट्स हैं: J JV JVM V VM M
स्पष्टीकरण और विश्लेषण
- सबस्ट्रिंग्स की कुल संख्या: लंबाई n की स्ट्रिंग के लिए = n(n+1)/2
- समय जटिलता: O(n²) - दो नेस्टेड लूप्स
- स्पेस जटिलता: O(n²) - सभी सबस्ट्रिंग्स स्टोर करने के लिए
- सबस्ट्रिंग बनाम सबसिक्वेंस: सबस्ट्रिंग सन्निहित होते हैं, सबसिक्वेंस नहीं (2^n - 1 संभावनाएं)
बेहतर दृष्टिकोण: Stream API (Java 8+)
public static ListgetAllSubstrings(String str) { return IntStream.range(0, str.length()) .boxed() .flatMap(i -> IntStream.rangeClosed(i + 1, str.length()) .mapToObj(j -> str.substring(i, j))) .collect(Collectors.toList()); } // उपयोग List substrings = getAllSubstrings("JVM"); substrings.forEach(System.out::println);
सबसेट्स (पावर सेट) बनाम सबस्ट्रिंग्स
| अवधारणा | परिभाषा | गिनती | उदाहरण "abc" |
|---|---|---|---|
| सबस्ट्रिंग्स | सन्निहित कैरेक्टर अनुक्रम | n(n+1)/2 | a, b, c, ab, bc, abc |
| सबसिक्वेंस | ऑर्डर बनाए रखते हुए कोई भी कैरेक्टर्स | 2^n - 1 | a, b, c, ab, ac, bc, abc |
| सबसेट्स (पावर सेट) | कैरेक्टर्स का कोई भी संयोजन | 2^n | ∅, a, b, c, ab, ac, bc, abc |
पावर सेट जनरेशन (सभी सबसेट्स)
public static ListpowerSet(String str) { List result = new ArrayList<>(); int n = str.length(); int total = 1 << n; // 2^n for (int mask = 0; mask < total; mask++) { StringBuilder subset = new StringBuilder(); for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) { subset.append(str.charAt(i)); } } result.add(subset.toString()); } return result; } // "abc" के लिए: "", "a", "b", "ab", "c", "ac", "bc", "abc"
सामान्य उपयोग के मामले
- पैटर्न मिलान: टेक्स्ट में सभी संभावित पैटर्न खोजना
- डीएनए अनुक्रम विश्लेषण: सामान्य सबस्ट्रिंग्स पहचानना
- ऑटोकंप्लीट: प्रीफिक्स-आधारित सुझाव
- पैलिंड्रोम डिटेक्शन: सभी सबस्ट्रिंग्स चेक करना
- कम्प्रेशन एल्गोरिदम: दोहराए जाने वाले पैटर्न खोजना