Dada una array arr[] de longitud N que consta solo de letras mayúsculas en inglés y una letra ch . la tarea es encontrar la array final que se formará invirtiendo el prefijo cada vez que se encuentre la letra ch en la array.
Ejemplos :
Entrada : arr[] = {‘A’, ‘B’, ‘X’, ‘C’, ‘D’, ‘X’, ‘F’}, ch= ‘X’
Salida : DCXABXF
Explicación :
Primer encuentro de ‘ X’ en el índice 2, Subconjunto inicial = A, B, Subconjunto final = B, A, X.
Segundo encuentro de ‘X’ en el índice 5, Subconjunto inicial = B, A, X, C, D
Subconjunto final = D, C , X, A, B, X (agregado).
Subconjunto final después de atravesar, = D, C, X, A, B, X, FEntrada : arr[] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’}, ch = ‘F’
Salida : ABCDE
Planteamiento : La idea para resolver el problema es la siguiente:
Si cada porción entre dos ocurrencias de ch (o los extremos de la array) se considera un segmento, entonces las inversiones de prefijo de la string se pueden visualizar como agregando los caracteres de un segmento alternativamente al principio y al final de la string y seguir expandiéndose. hacia fuera.
- Entonces, la idea es empujar el elemento de la array al final de una lista hasta que ch ocurra por primera vez.
- Cuando ocurra el primer ch , empuje los elementos, incluido ch , al frente de la lista hasta que ocurra el siguiente ch . Nuevamente, si ocurre ch , empuje los elementos al final de la lista, incluido ch .
- Entonces, la conclusión es que cada vez que ocurre ch , tienes que cambiar la dirección de empuje de los elementos.
Nota : si hay un número impar de K en la array, debe invertir la lista a medida que comenzamos a empujar el elemento desde atrás.
Siga los pasos que se detallan a continuación
- Crea una lista llamada li para almacenar los elementos .
- Cree una variable llamada encontrada para verificar de qué lado tiene que agregar los elementos
- Si ocurre ch , cambie el valor de encontrado de 1 a 0 o de 0 a 1.
- Si encontrado es igual a 1 , agregue los elementos al frente .
- De lo contrario, agregue los elementos en la parte posterior.
- Si ch ocurre un número impar de veces, invierta la lista e imprima, de lo contrario imprímala simplemente
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Final string after performing all the // operations list<char> findFinalString(char* arr, int n, char ch) { list<char> li; bool found = 0; for (int i = 0; i < n; i++) { // ch Found if (arr[i] == ch) found = !found; // Push character at front of list if (found) li.push_front(arr[i]); // Push character at back of list else li.push_back(arr[i]); } // If there is odd number of ch if (found == 1) li.reverse(); // Return the list return li; } // Driver Code int main() { char arr[] = { 'A', 'B', 'X', 'C', 'D', 'X', 'F' }; char ch = 'X'; int N = sizeof(arr) / sizeof(arr[0]); // Function call list<char> ans = findFinalString(arr, N, ch); for (auto itr = ans.begin(); itr != ans.end(); itr++) cout << *itr << " "; return 0; }
D C X A B X F
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA