Compruebe si una string se puede convertir en otra string dada mediante la eliminación de una substring

Posted on by Rudeus Greyrat

Dadas dos strings S y T de longitud N y M respectivamente, la tarea es comprobar si la string S se puede convertir en la string T eliminando como máximo una substring de la string S. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO» .

Ejemplo:

Entrada: S = “abcdef”, T = “abc” 
Salida: SÍ 
Explicación: 
Al eliminar la substring { S[3], …, S[5] } se modifica S a “abc”. 
Dado que la string S es igual a T, la salida requerida es «SÍ».

Entrada: S = “aaabbb”, T = “ab” 
Salida: SÍ 
Explicación: 
Eliminar la substring { S[1], …, S[4] } modifica S a “ab”. 
Dado que la string S es igual a T, la salida requerida es «SÍ».

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las substrings posibles de la string S y, para cada substring, verificar si su eliminación hace que la string S sea igual a la string T o no. Si se encuentra que es cierto para cualquier string, imprima «SÍ» . De lo contrario, escriba «NO» . 
Complejidad temporal: O(N 2 * M)  
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

Si la substring { S[0], …, S[i] } + { S[N – (M – i)], …, S[N – 1] } es igual a T , solo entonces, la string S puede ser convertido a la string T .

Siga los pasos a continuación para resolver el problema:

  • Iterar sobre el rango [0, M] y comprobar si la substring { S[0], …, S[i] } + { S[N – (M – i)], …, S[N – 1] } es igual a T o no. Si se encuentra que es cierto, escriba «SÍ» .
  • De lo contrario, escriba «NO» .

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if S can be converted to T
// by removing at most one substring from S
string make_string_S_to_T(string S, string T)
{
    // Check if S can be converted to T by
    // removing at most one substring from S
    bool possible = false;
 
    // Stores length of string T
    int M = T.length();
 
    // Stores length of string S
    int N = S.length();
 
    // Iterate over the range [0, M - 1]
    for (int i = 0; i <= M; i++) {
 
        // Stores Length of the substring
        // { S[0], ..., S[i] }
        int prefix_length = i;
 
        // Stores Length of the substring
        // { S[0], ..., S[i] }
        int suffix_length = M - i;
 
        // Stores prefix substring
        string prefix
            = S.substr(0, prefix_length);
 
        // Stores suffix substring
        string suffix
            = S.substr(N - suffix_length,
                       suffix_length);
 
        // Checking if prefix+suffix == T
        if (prefix + suffix == T) {
            possible = true;
            break;
        }
    }
 
    if (possible)
        return "YES";
    else
        return "NO";
}
 
// Driver Code
int main()
{
    // Given String S and T
    string S = "ababcdcd";
    string T = "abcd";
 
    // Function call
    cout << make_string_S_to_T(S, T);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
// Function to check if S can be converted to T
// by removing at most one subString from S
static String make_String_S_to_T(String S, String T)
{
   
    // Check if S can be converted to T by
    // removing at most one subString from S
    boolean possible = false;
 
    // Stores length of String T
    int M = T.length();
 
    // Stores length of String S
    int N = S.length();
 
    // Iterate over the range [0, M - 1]
    for (int i = 0; i <= M; i++)
    {
 
        // Stores Length of the subString
        // { S[0], ..., S[i] }
        int prefix_length = i;
 
        // Stores Length of the subString
        // { S[0], ..., S[i] }
        int suffix_length = M - i;
 
        // Stores prefix subString
        String prefix
            = S.substring(0, prefix_length);
 
        // Stores suffix subString
        String suffix
            = S.substring(N - suffix_length,
                       N);
 
        // Checking if prefix+suffix == T
        if ((prefix + suffix).equals(T))
        {
            possible = true;
            break;
        }
    }
    if (possible)
        return "YES";
    else
        return "NO";
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given String S and T
    String S = "ababcdcd";
    String T = "abcd";
 
    // Function call
    System.out.print(make_String_S_to_T(S, T));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python program for the above approach
 
# Function to check if S can be converted to T
# by removing at most one substring from S
def make_string_S_to_T(S, T):
     
    # Check if S can be converted to T by
    # removing at most one substring from S
    possible = False
     
    # Stores length of string T
    M = len(T)
     
    # Stores length of string S
    N = len(S)
     
    # Iterate over the range [0, M - 1]
    for i in range(0,M+1):
         
        # Stores Length of the substring
        #  S[0], ..., S[i]
        prefix_length = i
         
        # Stores Length of the substring
        #  S[0], ..., S[i]
        suffix_length = M - i
         
        # Stores prefix substring
        prefix = S[:prefix_length]
         
        # Stores suffix substring
        suffix = S[N - suffix_length:N]
         
        # Checking if prefix+suffix == T
        if (prefix + suffix == T):
            possible = True
            break
     
    if (possible):
        return "YES"
    else:
        return "NO"
 
# Driver Code
 
# Given String S and T
S = "ababcdcd"
T = "abcd"
 
# Function call
print(make_string_S_to_T(S, T))
 
# This code is contributed by shubhamsingh10

C#

// C# program to implement
// the above approach
using System;
public class GFG
{
 
// Function to check if S can be converted to T
// by removing at most one subString from S
static String make_String_S_to_T(String S, String T)
{
   
    // Check if S can be converted to T by
    // removing at most one subString from S
    bool possible = false;
 
    // Stores length of String T
    int M = T.Length;
 
    // Stores length of String S
    int N = S.Length;
 
    // Iterate over the range [0, M - 1]
    for (int i = 0; i <= M; i++)
    {
 
        // Stores Length of the subString
        // { S[0], ..., S[i] }
        int prefix_length = i;
 
        // Stores Length of the subString
        // { S[0], ..., S[i] }
        int suffix_length = M - i;
 
        // Stores prefix subString
        String prefix
            = S.Substring(0, prefix_length);
 
        // Stores suffix subString
        String suffix
            = S.Substring(N-suffix_length,
                       suffix_length);
 
        // Checking if prefix+suffix == T
        if ((prefix + suffix).Equals(T))
        {
            possible = true;
            break;
        }
    }
    if (possible)
        return "YES";
    else
        return "NO";
}
 
// Driver Code
public static void Main(String[] args)
{
   
    // Given String S and T
    String S = "ababcdcd";
    String T = "abcd";
 
    // Function call
    Console.Write(make_String_S_to_T(S, T));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to check if S can be converted to T
    // by removing at most one subString from S
     function make_String_S_to_T( S,  T) {
 
        // Check if S can be converted to T by
        // removing at most one subString from S
        var possible = false;
 
        // Stores length of String T
        var M = T.length;
 
        // Stores length of String S
        var N = S.length;
 
        // Iterate over the range [0, M - 1]
        for (i = 0; i <= M; i++) {
 
            // Stores Length of the subString
            // { S[0], ..., S[i] }
            var prefix_length = i;
 
            // Stores Length of the subString
            // { S[0], ..., S[i] }
            var suffix_length = M - i;
 
            // Stores prefix subString
            var prefix = S.substring(0, prefix_length);
 
            // Stores suffix subString
            var suffix = S.substring(N - suffix_length, N);
 
            // Checking if prefix+suffix == T
            if ((prefix + suffix)==(T)) {
                possible = true;
                break;
            }
        }
        if (possible)
            return "YES";
        else
            return "NO";
    }
 
    // Driver Code
     
 
        // Given String S and T
        var S = "ababcdcd";
        var T = "abcd";
 
        // Function call
        document.write(make_String_S_to_T(S, T));
 
// This code is contributed by todaysgaurav
 
</script>
Producción: 

YES

 

Complejidad temporal: O(M 2 )
Espacio auxiliar: O(M)

Publicación traducida automáticamente

Artículo escrito por nk14646 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *