Dada una string, devuelve todas las subsecuencias posibles que comienzan con una vocal y terminan con una consonante. Una String es una subsecuencia de una String dada, que se genera eliminando algún carácter de una string dada sin cambiar su orden.
Ejemplos:
Input : 'abc' Output : ab, ac, abc Input : 'aab' Output : ab, aab
Fuente de la pregunta: Yatra.com Experiencia de entrevista | conjunto 7
Explicación del Algoritmo:
- Paso 1: iterar sobre toda la string
- Paso 2: comprobar si el i-ésimo carácter de vocal
- Paso 3: si es verdadero iterar la string desde el final,
si es falso pasar a la siguiente iteración- Paso 4: verifique el carácter j-ésimo para la consonante
si es falso, muévase a la siguiente iteración
si es verdadero, realice lo siguiente- Paso 5: agregue la substring que comienza en el índice i y finaliza en el índice j al conjunto hash.
- Paso 6: iterar sobre la substring, soltar cada carácter y repetir para generar toda su substring
C++
// C++ program to generate all the subse-quence // starting with vowel and ending with consonant. #include <bits/stdc++.h> using namespace std; // Set to store all the subsequences set<string> st; // Utility method to check vowel bool isVowel(char c) { return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'); } // Utility method to check consonant bool isConsonant(char c) { return !isVowel(c); } // It computes all the possible substring that // starts with vowel and end with consonant void subsequence(string str) { // iterate over the entire string for (int i = 0; i < str.length(); i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for (int j = str.length() - 1; j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset string str_sub = str.substr(i, j + 1); st.insert(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for (int k = 1; k < str_sub.length() - 1; k++) { string sb = str_sub; sb.erase(sb.begin() + k); subsequence(sb); } } } } } } // Driver Code int main() { string s = "xabcef"; subsequence(s); for (auto i : st) cout << i << " "; cout << endl; return 0; } // This code is contributed by // sanjeev2552
Java
// Java Program to generate all the subsequence // starting with vowel and ending with consonant. import java.util.HashSet; public class Subsequence { // Set to store all the subsequences static HashSet<String> st = new HashSet<>(); // It computes all the possible substring that // starts with vowel and end with consonent static void subsequence(String str) { // iterate over the entire string for (int i = 0; i < str.length(); i++) { // test ith character for vowel if (isVowel(str.charAt(i))) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for (int j = (str.length() - 1); j >= i; j--) { // test jth character for consonant. if (isConsonant(str.charAt((j)))) { // once we get a consonant add it to // the hashset String str_sub = str.substring(i, j + 1); st.add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for (int k = 1; k < str_sub.length() - 1; k++) { StringBuffer sb = new StringBuffer(str_sub); sb.deleteCharAt(k); subsequence(sb.toString()); } } } } } } // Utility method to check vowel static boolean isVowel(char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); } // Utility method to check consonant static boolean isConsonant(char c) { return !isVowel(c); } // Driver code public static void main(String[] args) { String s = "xabcef"; subsequence(s); System.out.println(st); } }
Python3
# Python program to generate all the subse-quence # starting with vowel and ending with consonant. # Set to store all the subsequences st = set() # Utility method to check vowel def isVowel(c): return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u') # Utility method to check consonant def isConsonant(c): return not isVowel(c) # It computes all the possible substring that # starts with vowel and end with consonant def subsequence(Str): global st # iterate over the entire string for i in range(len(Str)): # test ith character for vowel if (isVowel(Str[i])): # if the ith character is vowel # iterate from end of the string # and check for consonant. for j in range(len(Str) - 1,i-1,-1): # test jth character for consonant. if (isConsonant(Str[j])): # once we get a consonant add it to # the hashset str_sub = Str[i : i + j + 1] st.add(str_sub) # drop each character of the substring # and recur to generate all subsequence # of the substring for k in range(1,len(str_sub)): sb = str_sub sb = sb.replace(sb[k],"") subsequence(sb) # Driver Code s = "xabcef" subsequence(s) for i in st: print(i,end = " ") print() # This code is contributed by shinjanpatra
C#
// C# Program to generate all the subsequence // starting with vowel and ending with consonant. using System; using System.Collections.Generic; using System.Text; class Subsequence { // Set to store all the subsequences static HashSet<String> st = new HashSet<String>(); // It computes all the possible substring that // starts with vowel and end with consonent static void subsequence(String str) { // iterate over the entire string for (int i = 0; i < str.Length; i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for (int j = (str.Length - 1); j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset String str_sub = str.Substring(i, j -i + 1); st.Add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for (int k = 1; k < str_sub.Length - 1; k++) { StringBuilder sb = new StringBuilder(str_sub); sb.Remove(k, 1); subsequence(sb.ToString()); } } } } } } // Utility method to check vowel static bool isVowel(char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); } // Utility method to check consonant static bool isConsonant(char c) { return !isVowel(c); } // Driver code public static void Main(String[] args) { String s = "xabcef"; subsequence(s); foreach(String str in st) Console.Write(str + ", "); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript program to generate all the subse-quence // starting with vowel and ending with consonant. // Set to store all the subsequences let st = new Set(); // Utility method to check vowel function isVowel(c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'); } // Utility method to check consonant function isConsonant(c) { return !isVowel(c); } // It computes all the possible substring that // starts with vowel and end with consonant function subsequence(str) { // iterate over the entire string for (let i = 0; i < str.length; i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for (let j = str.length - 1; j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset let str_sub = str.substring(i, i + j + 1); st.add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for (let k = 1; k < str_sub.length - 1; k++) { let sb = str_sub; sb = sb.replace(sb[k],""); subsequence(sb); } } } } } } // Driver Code let s = "xabcef"; subsequence(s); for (let i of st) document.write(i," "); document.write("</br>"); // This code is contributed by shinjanpatra </script>
ab abc abce abcef abcf abef abf ac acef acf aef af ef
Este artículo es una contribución de Sumit Ghosh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA