Compruebe si la string S1 se puede formar mediante inserciones repetidas de otra string S2

Dadas dos strings S1 y S2 que consisten en caracteres únicos, la tarea es verificar que S1 se pueda formar mediante inserciones repetidas de la string S2 .

Entrada: S1 = “aabb”, S2 = “ab”
Salida: Sí
Explicación: la string mencionada se puede obtener después de una serie de movimientos:

• Inserte la string «ab» en una string vacía. La string actual será » ab «
• inserte «ab» después de «a». La string final será «a ab b»

Entrada: S1 = “ababcd”, S2 = “abc”
Salida: No
Explicación: No es posible obtener la string anterior con ninguna serie de movimientos.

Enfoque: el problema dado se puede resolver utilizando la estructura de datos de pila . La idea es insertar los caracteres de S1 en la pila hasta encontrar el último carácter de S2. Luego extraiga los caracteres de longitud (S2) de Stack y compárelos con S2. Si no es lo mismo, deténgase y devuelva falso. De lo contrario, repita el proceso hasta que S1 quede vacío.

A continuación se muestran los pasos para el enfoque anterior:

• Primero, verifique los casos a continuación y devuelva falso si se encuentra verdadero:
  • El recuento de caracteres únicos en S1 debe ser el mismo que en S2
  • La longitud de la string S1 debe ser un múltiplo de S2
• Mantener una pila para todos los personajes.
• Iterar a través de la string S1 y empujar caracteres en una pila
• Si el carácter actual es el último carácter de la string S2 , haga coincidir todos los caracteres a la izquierda en la pila
• Si para cualquier posición la pila está vacía o el carácter no coincide, devuelve Falso
• Después de la iteración completa en la string, verifique si la pila está vacía. Si la pila no está vacía, devuelve falso; de lo contrario, devuelve verdadero

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check a valid insertion
bool validInsertionstring(string S1, string S2)
{
 
    // Store the size of string
    int N = S1.length();
    int M = S2.length();
 
    // Maintain a stack for characters
    stack<char> st;
 
    // Iterate through the string
    for (int i = 0; i < N; i++) {
 
        // push the current character
        // on top of the stack
        st.push(S1[i]);
 
        // If the current character is the
        // last character of string S2 then
        // pop characters until S2 is not formed
        if (S1[i] == S2[M - 1]) {
 
            // index of last character of the string S2
            int idx = M - 1;
 
            // pop characters till 0-th index
            while (idx >= 0) {
                if (st.empty()) {
                    return false;
                }
                char c = st.top();
                st.pop();
                if (c != S2[idx]) {
                    return false;
                }
                idx--;
            }
        }
    }
 
    // Check if stack in non-empty
    if (!st.empty()) {
        return false;
    }
    else {
        return true;
    }
}
 
// Driver Code
int main()
{
    string S1 = "aabb";
    string S2 = "ab";
    validInsertionstring(S1, S2) ? cout << "Yes\n"
                                 : cout << "No\n";
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
   
    // Function to check a valid insertion
    static boolean validInsertionstring(String S1,
                                        String S2)
    {
 
        // Store the size of string
        int N = S1.length();
        int M = S2.length();
 
        // Maintain a stack for characters
        Stack<Character> st = new Stack<>();
 
        // Iterate through the string
        for (int i = 0; i < N; i++) {
 
            // push the current character
            // on top of the stack
            st.push(S1.charAt(i));
 
            // If the current character is the
            // last character of string S2 then
            // pop characters until S2 is not formed
            if (S1.charAt(i) == S2.charAt(M - 1)) {
 
                // index of last character of the string S2
                int idx = M - 1;
 
                // pop characters till 0-th index
                while (idx >= 0) {
                    if (st.size() == 0) {
                        return false;
                    }
                    char c = st.peek();
                    st.pop();
                    if (c != S2.charAt(idx)) {
                        return false;
                    }
                    idx--;
                }
            }
        }
 
        // Check if stack in non-empty
        if (st.size() > 0) {
            return false;
        }
        else {
            return true;
        }
    }
   
  // Driver code
    public static void main(String[] args)
    {
        String S1 = "aabb";
        String S2 = "ab";
        if (validInsertionstring(S1, S2) == true)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by Potta Lokesh

# Python3 implementation for the above approach
 
# Function to check a valid insertion
def validInsertionstring(S1, S2):
    # Store the size of string
    N = len(S1)
    M = len(S2)
 
    # Maintain a stack for characters
    st = []
 
    # Iterate through the string
    for i in range(N):
        # push the current character
        # on top of the stack
        st.append(S1[i])
 
        # If the current character is the
        # last character of string S2 then
        # pop characters until S2 is not formed
        if (S1[i] == S2[M - 1]):
            # index of last character of the string S2
            idx = M - 1
 
            # pop characters till 0-th index
            while (idx >= 0):
                if (len(st) == 0):
                    return False
                c = st[-1]
                st.pop()
                if (c != S2[idx]):
                    return False
                idx-=1
 
    # Check if stack in non-empty
    if (len(st) != 0):
        return False
    else:
        return True
 
S1 = "aabb"
S2 = "ab"
if validInsertionstring(S1, S2):
    print("Yes")
else:
    print("No")
     
    # This code is contributed by divyeshrabadiya07.

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to check a valid insertion
static bool validInsertionstring(string S1, string S2)
{
 
    // Store the size of string
    int N = S1.Length;
    int M = S2.Length;
 
    // Maintain a stack for characters
    Stack<char> st = new Stack<char>();
 
    // Iterate through the string
    for (int i = 0; i < N; i++) {
 
        // push the current character
        // on top of the stack
        st.Push(S1[i]);
 
        // If the current character is the
        // last character of string S2 then
        // pop characters until S2 is not formed
        if (S1[i] == S2[M - 1]) {
 
            // index of last character of the string S2
            int idx = M - 1;
 
            // pop characters till 0-th index
            while (idx >= 0) {
                if (st.Count==0) {
                    return false;
                }
                char c = st.Peek();
                st.Pop();
                if (c != S2[idx]) {
                    return false;
                }
                idx--;
            }
        }
    }
 
    // Check if stack in non-empty
    if (st.Count > 0) {
        return false;
    }
    else {
        return true;
    }
}
 
// Driver Code
public static void Main()
{
    string S1 = "aabb";
    string S2 = "ab";
    if(validInsertionstring(S1, S2)==true)
     Console.Write("Yes");
    else
     Console.Write("No");
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
    // Javascript implementation for the above approach
     
    // Function to check a valid insertion
    function validInsertionstring(S1, S2)
    {
 
        // Store the size of string
        let N = S1.length;
        let M = S2.length;
 
        // Maintain a stack for characters
        let st = [];
 
        // Iterate through the string
        for (let i = 0; i < N; i++) {
 
            // push the current character
            // on top of the stack
            st.push(S1[i]);
 
            // If the current character is the
            // last character of string S2 then
            // pop characters until S2 is not formed
            if (S1[i] == S2[M - 1]) {
 
                // index of last character of the string S2
                let idx = M - 1;
 
                // pop characters till 0-th index
                while (idx >= 0) {
                    if (st.length == 0) {
                        return false;
                    }
                    let c = st[st.length - 1];
                    st.pop();
                    if (c != S2[idx]) {
                        return false;
                    }
                    idx--;
                }
            }
        }
 
        // Check if stack in non-empty
        if (st.length != 0) {
            return false;
        }
        else {
            return true;
        }
    }
     
    let S1 = "aabb";
    let S2 = "ab";
    validInsertionstring(S1, S2) ? document.write("Yes")
                                 : document.write("No");
 
// This code is contributed by suresh07.
</script>

Yes

Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)