Compruebe si las strings dadas se pueden igualar insertando como máximo 1 string

Dadas dos oraciones S1 y S2 , la tarea es verificar si las oraciones pueden igualarse insertando como máximo una oración (posiblemente, vacía) en cualquiera de las dos oraciones.

Ejemplos:

Entrada: S1 = «Empezar a practicar en GeeksforGeeks», S2 = «Iniciar GeeksforGeeeks»   
Salida: 
Verdadero
Explicación: se puede insertar «practicando en» entre «Inicio» y «GeeksforGeeks» en s2 para que sea igual a S1.

Entrada: S1= “Nueva Delhi es la capital de INDIA”, S2= “es la capital de”   
Salida: 
Falso

Enfoque: Las siguientes observaciones ayudan a resolver el problema:

• Si los tamaños de dos oraciones son iguales, pero ellos mismos no son iguales, no pueden hacerse iguales.
• Después de eliminar el prefijo común más largo y el sufijo común más largo de las dos oraciones, si al menos una de ellas está vacía, significa que se pueden hacer iguales.

El problema se puede resolver con la ayuda de deques . Siga los pasos a continuación para resolver el problema:

• Compruebe si el tamaño de S1 y S2 son iguales. Si son iguales, haz lo siguiente:
  • Si S1 es igual a S2 , devuelve verdadero .
  • De lo contrario, devuelve falso .
• Inicialice dos deques X e Y .
• Inserte todas las palabras de S1 en X .
• Inserte todas las palabras de S2 en Y .
• Si bien los frentes de X e Y son iguales , salte desde los frentes de X e Y.
• Si bien los dorsos de X e Y son iguales, salta desde los dorsos de X e Y .
• Compruebe si alguno de X o Y está vacío. Si alguno de ellos está vacío, devuelve verdadero .
• De lo contrario, devuelve falso .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether
// two sentences can be made equal
// by inserting at most
// one sentence in one of them
bool areSimilar(string S1, string S2)
{
    // size of sentence S1
    int N = S1.size();
 
    // size of sentence S2
    int M = S2.size();
 
    // check if S1 and S2
    // are of equal sizes
    if (N == M) {
        // if both sentences are
        // the same, return true
        if (S1 == S2)
            return true;
 
        // Otherwise, return false
        return false;
    }
 
    // Declare 2 deques X and Y
    deque<string> X, Y;
 
    // insert ' ' at the end of both
    // sentences so that the last
    // word can be identified
    S1.push_back(' ');
    S2.push_back(' ');
 
    string temp = "";
 
    // traverse the sentence S1
    for (int i = 0; i < N + 1; i++) {
 
        // push temp in deque
        // when a space comes in sentence
        // i.e a word has been formed
        if (S1[i] == ' ') {
            X.push_back(temp);
            temp = "";
        }
        else {
            // temp stores words
            // of the sentence
            temp += S1[i];
        }
    }
 
    // traverse the sentence S1
    for (int i = 0; i < M + 1; i++) {
 
        // push temp in deque
        // when a space comes in sentence
        // i.e a word has been formed
        if (S2[i] == ' ') {
            Y.push_back(temp);
            temp = "";
        }
        else {
            // temp stores words of the sentence
            temp += S2[i];
        }
    }
 
    // check for prefixes of both sentences
    while (X.size() > 0 && Y.size() > 0
           && X.front() == Y.front()) {
 
        // pop the prefix from both
        // deques till they are equal
        X.pop_front();
        Y.pop_front();
    }
 
    // check for suffixes of both sentences
    while (X.size() > 0 && Y.size() > 0
           && X.back() == Y.back()) {
 
        // pop the suffix from both deques
        // till they are equal
        X.pop_back();
        Y.pop_back();
    }
 
    // if any of the deques is empty
    // return true
    if (X.size() == 0 || Y.size() == 0)
        return true;
 
    // if both the deques are
    // not empty return false
    return false;
}
// Driver code
int main()
{
    // Input
    string S1 = "Start practicing on GeeksforGeeks";
    string S2 = "Start GeeksforGeeks";
 
    // function call
    if (areSimilar(S1, S2))
        cout << "True" << endl;
    else
        cout << "False" << endl;
    return 0;
}

# Python3 program for the above approach
from collections import deque
 
# Function to check whether
# two sentences can be made equal
# by inserting at most
# one sentence in one of them
def areSimilar(S1, S2):
     
    S1 = [i for i in S1]
    S2 = [i for i in S2]
     
    # Size of sentence S1
    N = len(S1)
 
    # Size of sentence S2
    M = len(S2)
 
    # Check if S1 and S2
    # are of equal sizes
    if (N == M):
         
        # If both sentences are
        # the same, return True
        if (S1 == S2):
            return True
 
        # Otherwise, return false
        return False
 
    # Declare 2 deques X and Y
    X, Y = deque(), deque()
 
    # Insert ' ' at the end of both
    # sentences so that the last
    # word can be identified
    S1.append(' ')
    S2.append(' ')
 
    temp = ""
 
    # Traverse the sentence S1
    for i in range(N + 1):
         
        # Push temp in deque
        # when a space comes in sentence
        # i.e a word has been formed
        if (S1[i] == ' '):
            X.append(temp)
            temp = ""
        else:
             
            # temp stores words
            # of the sentence
            temp += S1[i]
 
    # Traverse the sentence S1
    for i in range(M + 1):
         
        # Push temp in deque
        # when a space comes in sentence
        # i.e a word has been formed
        if (S2[i] == ' '):
            Y.append(temp)
            temp = ""
        else:
             
            # temp stores words of the sentence
            temp += S2[i]
 
    # Check for prefixes of both sentences
    while (len(X) > 0 and
           len(Y) > 0 and X[0] == Y[0]):
 
        # Pop the prefix from both
        # deques till they are equal
        X.popleft()
        Y.popleft()
 
    # Check for suffixes of both sentences
    while (len(X) > 0 and len(Y) > 0 and
           X[-1] == Y[-1]):
                
        # Pop the suffix from both deques
        # till they are equal
        X.pop()
        Y.pop()
 
    # If any of the deques is empty
    # return True
    if (len(X) == 0 or len(Y) == 0):
        return True
 
    # If both the deques are
    # not empty return false
    return False
 
# Driver code
if __name__ == '__main__':
     
    # Input
    S1 = "Start practicing on GeeksforGeeks"
    S2 = "Start GeeksforGeeks"
 
    # Function call
    if (areSimilar(S1, S2)):
        print("True")
    else:
        print("False")
 
# This code is contributed by mohit kumar 29

True

Complejidad temporal: O(N+M), donde N y M son los tamaños de S1 y S2 respectivamente.
Espacio Auxiliar: O(N+M)