Verifique si String S se puede comprimir a T reemplazando algunos caracteres X con el conteo X

Dadas dos strings, S y T , donde S es una string normal y T es  una string comprimida, la tarea es determinar si la string comprimida T se puede lograr comprimiendo la string S.

Nota: Un mecanismo de compresión puede eliminar arbitrariamente X (X >= 0) caracteres y reemplazarlos con el recuento de caracteres eliminados (X). 

Ejemplos:

Entrada: S = “HELLOWORLD” T=”H2L4L1″
Salida: Verdadero
Explicación: 
Reemplace los índices 1 a 2 en “H EL LOWORLD” con el conteo 2 -> “H 2 LOWORLD”
Reemplace los índices 4 a 7 en “HELL OWOR LD” con conteo 4 -> “H2L 4 LD”
Reemplace el índice 9 en “HELLOWORL D ” con el conteo 1 -> “H2L4L 1 ”
La string resultante es la misma que T. Por lo tanto, la string S se puede comprimir a T.

Entrada: S = «DFS» T = «D1D»
Salida: Falso
Explicación: podemos ver claramente que T no es una string comprimida válida para S, ya que la string comprimida T termina en «D», que no es similar a la string anterior S .

Enfoque: la idea es simplemente atravesar la string y hacer coincidir los caracteres de la siguiente manera:

• Compare los caracteres en los índices correspondientes en S y T,
• Del mismo modo, omita el recuento de índices entre dos alfabetos en T.

Ilustración:

Considere S = «HELLOWORLD» T = «H2L4L1»

En una string comprimida, 2 es el número entero entre ‘H’ y ‘L’, por lo que la string S debe tener dos caracteres entre ‘H’ y ‘L’, y tiene (H EL LOWORLD ) .

Luego, el siguiente número entero es 4 entre ‘L’ y ‘L’, luego verifique si String S tiene 4 caracteres o no, (HELL OWOR LD)

Y el último entero es 1 después del carácter ‘L’ y String también tiene 1 carácter (es decir, ‘D’) después de ‘L’. (HOLA MUNDO D )

Entonces, esta string comprimida es válida. 

S = “ H EL BAJO LOWOR L D ” T=”H 2 L 4 L 1 “

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

• Comience a atravesar la cuerda S y T hasta su longitud simultáneamente.
• Verifique si T[i] es un número o no, si no es un número, compare S[j] y T[i] si no son iguales, luego devuelva directamente 0; de lo contrario, continúe e incremente j en 1.
• Si T[i] es un número, aumente la j a ese número hasta que obtengamos números en la string T.
• Incremente i en 1 hasta la longitud de T.
• Si j no es igual a S de longitud, devuelve 0.
• Si se cumplen todas las condiciones, devuelve 1 por fin.

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

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Return 1 if char c is number
boolean isnum(char c) { return (c >= 48 && c <= 57); }
 
// Function to check
// If string is compressed or not
int checkCompressed(string S, string T)
{
    int i = 0, j = 0;
 
    // Iterate till S.length()
    // And T.length
    while (j < S.length() && i < T.length()) {
        if (isnum(T[i]) == false) {
 
            // If its not equal
            // Then return 0
            if (S[j] != T[i]) {
                return 0;
            }
            j++;
        }
        else {
            int ans = T[i] - 48;
 
            // Iterate till we get number
            // In T string
            while (isnum(T[++i])) {
                ans *= 10;
                ans += T[i] - 48;
            }
            j += ans;
            i--;
        }
        i++;
    }
 
    // It j not equal to S string length
    // Then return 0
    if (j != S.length()) {
        return 0;
    }
    return 1;
}
 
// Driver code
int main()
{
    string S = "HelloWorld";
    string T = "H2l4l1";
    cout << checkCompressed(S, T) << endl;
    return 0;
}

// Java code for the above approach:
import java.util.*;
 
class GFG{
 
// Return 1 if char c is number
static boolean isnum(char c) { return (c >= 48 && c <= 57); }
 
// Function to check
// If String is compressed or not
static int checkCompressed(char[] S, char[] T)
{
    int i = 0, j = 0;
 
    // Iterate till S.length()
    // And T.length
    while (j < S.length && i < T.length) {
        if (isnum(T[i]) == false) {
 
            // If its not equal
            // Then return 0
            if (S[j] != T[i]) {
                return 0;
            }
            j++;
        }
        else {
            int ans = T[i] - 48;
 
            // Iterate till we get number
            // In T String
            while (i<T.length-1 && isnum(T[++i])) {
                 
                ans *= 10;
                ans += T[i] - 48;
            }
            j += ans;
            i--;
        }
        i++;
    }
 
    // It j not equal to S String length
    // Then return 0
    if (j != S.length) {
        return 0;
    }
    return 1;
}
 
// Driver code
public static void main(String[] args)
{
    String S = "HelloWorld";
    String T = "H2l4l1";
    System.out.print(checkCompressed(S.toCharArray(), T.toCharArray()) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

# python3 code for the above approach:
 
# Return 1 if char c is number
def isnum(c):
    return ord(c) >= 48 and ord(c) <= 57
 
# Function to check
# If string is compressed or not
def checkCompressed(S, T):
 
    i, j = 0, 0
 
    # Iterate till S.length()
    # And T.length
    while (j < len(S) and i < len(T)):
        if (isnum(T[i]) == False):
 
                        # If its not equal
                        # Then return 0
            if (S[j] != T[i]):
                return 0
 
            j += 1
 
        else:
            ans = ord(T[i]) - 48
 
            # Iterate till we get number
            # In T string
            i += 1
            while (i < len(T) and isnum(T[i])):
                ans *= 10
                ans += T[i] - 48
                i += 1
 
            j += ans
            i -= 1
 
        i += 1
 
        # It j not equal to S string length
        # Then return 0
    if (j != len(S)):
        return 0
 
    return 1
 
# Driver code
if __name__ == "__main__":
 
    S = "HelloWorld"
    T = "H2l4l1"
    print(checkCompressed(S, T))
 
    # This code is contributed by rakeshsahni

// C# code for the above approach:
using System;
 
public class GFG{
 
  // Return 1 if char c is number
  static boolean isnum(char c) { return (c >= 48 && c <= 57); }
 
  // Function to check
  // If String is compressed or not
  static int checkCompressed(char[] S, char[] T)
  {
    int i = 0, j = 0;
 
    // Iterate till S.length()
    // And T.length
    while (j < S.Length && i < T.Length) {
      if (isnum(T[i]) == false) {
 
        // If its not equal
        // Then return 0
        if (S[j] != T[i]) {
          return 0;
        }
        j++;
      }
      else {
        int ans = T[i] - 48;
 
        // Iterate till we get number
        // In T String
        while (i<T.Length-1 && isnum(T[++i])) {
 
          ans *= 10;
          ans += T[i] - 48;
        }
        j += ans;
        i--;
      }
      i++;
    }
 
    // It j not equal to S String length
    // Then return 0
    if (j != S.Length) {
      return 0;
    }
    return 1;
  }
 
  // Driver code
  static public void Main ()
  {
    string S = "HelloWorld";
    string T = "H2l4l1";
    Console.Write(checkCompressed(S.ToCharArray(), T.ToCharArray()) );
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
    // JavaScript Program of the above approach.
 
// Return 1 if char c is number
function isnum(c) { return (c>= 48 && c <= 57); }
  
// Function to check
// If string is compressed or not
function checkCompressed(S, T)
{
    let i = 0, j = 0;
  
    // Iterate till S.length()
    // And T.length
    while (j < S.length && i < T.length) {
        if (isnum(T[i].charCodeAt()) == false) {
  
            // If its not equal
            // Then return 0
            if (S[j] != T[i]) {
                return 0;
            }
            j++;
        }
        else {
            let ans = T[i].charCodeAt() - 48;
  
            // Iterate till we get number
            // In T string
            while (isnum(T[++i])) {
                ans *= 10;
                ans += T[i].charCodeAt() - 48;
            }
            j += ans;
            i--;
        }
        i++;
    }
  
    // It j not equal to S string length
    // Then return 0
    if (j != S.length) {
        return 0;
    }
    return 1;
}
 
    // Driver Code
    let S = "HelloWorld";
    let T = "H2l4l1";
    document.write( checkCompressed(S, T));
 
// This code is contributed by code_hunt.
</script>

1

Complejidad de tiempo: O(max (|S|, |T|) )
Espacio auxiliar: O(1)