Reconstruye la string original a partir de la string resultante en función de la técnica de codificación dada

Una string binaria S de longitud N se construye a partir de una string P de N caracteres y un entero X. La elección del i-ésimo carácter de S es la siguiente:

  • Si el carácter P i- X existe y es igual a 1, entonces S i es 1
  • si el carácter P i+ X existe y es igual a 1, entonces S i es 1
  • si las dos condiciones antes mencionadas son falsas, entonces Si es 0.

Dada la string resultante S y el entero X , reconstruya la string original P. Si ninguna string P puede producir la string S , genera -1.

Ejemplos:

Entrada : S = “10011”, X = 2
Salida : “01100”
Explicación : La string de entrada S = “10011” se puede construir a partir de la string de salida P = “01100”.

Entrada : S = “11101100111”, X = 3
Salida : -1
Explicación : La string de entrada S = “11101100111” no se puede construir a partir de ninguna string de salida P.

 

Enfoque: la tarea se puede resolver tomando una string auxiliar con todos 1s . Siga los pasos a continuación para resolver el problema:

  • Inicialice la string P con todos los caracteres como ‘1’.
  • Ahora recorra la string S usando un bucle y coloque ceros en las posiciones correctas en P de acuerdo con las condiciones dadas:
    • Si S [i] es igual a ‘0’ y P [i- X ] existe, i, e, (i- X )>=0, entonces ponga P [i- X ] = ‘0’.
    • Si S [i] es igual a ‘0’ y P [i+ X ] existe, es decir, (i+ X )< N , entonces ponga P [i+ X ] = ‘0’.
  • Inicialice una bandera variable = 1 para determinar si la string P existe o no.
  • Para verificar la exactitud de la string P construida , recorra la string S usando un bucle for:
    • Si S [i]==’1′ y P [i- X ] o P [i+ X ] existe y es igual a ‘1’, entonces la string P es correcta hasta ahora y el recorrido puede continuar.
    • Si S [i]==’1′ y P [i- X ] o P [i+ X ] no existe o no es igual a 1, entonces establezca el indicador = 0, emita -1 y salga del ciclo.
  • Si la bandera es igual a 0 después del recorrido de la string S , entonces genera la string original P .

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

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the original string P
void findString(string S, int X)
{
    // Stores the size of string S
    int N = S.size();
 
    // Each character of string
    // P is set to '1'
    string P(N, '1');
 
    // Loop to put zeroes at
    // the correct positions in P
    for (int i = 0; i < N; ++i) {
 
        // If the character is '0'
        if (S[i] == '0') {
 
            // If P[i-X] exists
            if (i - X >= 0) {
 
                // Set P[i-X] to '0'
                P[i - X] = '0';
            }
 
            // If P[i+X] exists
            if (i + X < N) {
 
                // Set P[i+X] to '0'
                P[i + X] = '0';
            }
        }
    }
 
    // Set flag to 1
    int flag = 1;
 
    // Loop to cross check
    // if P exists or not
    for (int i = 0; i < N; ++i) {
 
        // If the character is '1'
        if (S[i] == '1') {
 
            // If P[i-X] exists and
            // is equal to '1' or if
            // P[i+X] exists and
            // is equal to '1'
            if ((i - X >= 0
                 && P[i - X] == '1')
                || (i + X < N
                    && P[i + X] == '1')) {
                continue;
            }
            else {
 
                // Set flag to 0
                flag = 0;
 
                // Output -1
                cout << -1;
 
                // Break from the loop
                break;
            }
        }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
        // Output string P
        cout << P;
    }
}
 
// Driver Code
int main()
{
    // Given input
    string S = "10011";
    int X = 2;
 
    // Function Call
    findString(S, X);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Function to find the original string P
  static void findString(String S, int X)
  {
 
    // Stores the size of string S
    int N = S.length();
 
    // Each character of string
    // converted to char Array P
    // is set to '1'
    char[] P = new char[N];
    for (int i = 0; i < N; ++i) {
      P[i] = '1';
    }
 
    // Loop to put zeroes at
    // the correct positions in P
    for (int i = 0; i < N; ++i) {
 
      // If the character is '0'
      if (S.charAt(i) == '0') {
 
        // If P[i-X] exists
        if (i - X >= 0) {
 
          // Set P[i-X] to '0'
          P[i - X] = '0';
        }
 
        // If P[i+X] exists
        if (i + X < N) {
 
          // Set P[i+X] to '0'
          P[i + X] = '0';
        }
      }
    }
 
    // Set flag to 1
    int flag = 1;
 
    // Loop to cross check
    // if P exists or not
    for (int i = 0; i < N; ++i) {
 
      // If the character is '1'
      if (S.charAt(i) == '1') {
 
        // If P[i-X] exists and
        // is equal to '1' or if
        // P[i+X] exists and
        // is equal to '1'
        if ((i - X >= 0 && P[i - X] == '1')
            || (i + X < N && P[i + X] == '1')) {
          continue;
        }
        else {
 
          // Set flag to 0
          flag = 0;
 
          // Output -1
          System.out.print(-1);
 
          // Break from the loop
          break;
        }
      }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
      // Output string P
      String p = new String(P);
      System.out.print(p);
    }
  }
 
  // Driver Code
  public static void main(String args[])
  {
 
    // Given input
    String S = "10011";
    int X = 2;
 
    // Function Call
    findString(S, X);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python program for the above approach
 
# Function to find the original string P
def findString(S, X):
 
    # Stores the size of string S
    N = len(S)
 
    # Each character of string
    # P is set to '1'
    P = ['1'] * N
 
    # Loop to put zeroes at
    # the correct positions in P
    for i in range(N):
 
        # If the character is '0'
        if (S[i] == '0'):
 
            # If P[i-X] exists
            if (i - X >= 0):
 
                # Set P[i-X] to '0'
                P[i - X] = '0';
 
            # If P[i+X] exists
            if (i + X < N):
 
                # Set P[i+X] to '0'
                P[i + X] = '0';
 
    # Set flag to 1
    flag = 1;
 
    # Loop to cross check
    # if P exists or not
    for i in range(N):
 
        # If the character is '1'
        if (S[i] == '1'):
 
            # If P[i-X] exists and
            # is equal to '1' or if
            # P[i+X] exists and
            # is equal to '1'
            if ((i - X >= 0 and P[i - X] == '1') or (i + X < N and P[i + X] == '1')):
                continue;
            else:
 
                # Set flag to 0
                flag = 0;
 
                # Output -1
                print(-1);
 
                # Break from the loop
                break;
 
    # If flag is equal to 1
    if (flag == 1):
 
        # Output string P
        print("".join(P));
 
# Driver Code
 
# Given input
S = "10011";
X = 2;
 
# Function Call
findString(S, X);
 
# This code is contributed by gfgking

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG
{
 
  // Function to find the original string P
  static void findString(string S, int X)
  {
 
    // Stores the size of string S
    int N = S.Length;
 
    // Each character of string
    // converted to char Array P
    // is set to '1'
    char[] P = new char[N];
    for (int i = 0; i < N; ++i) {
      P[i] = '1';
    }
 
    // Loop to put zeroes at
    // the correct positions in P
    for (int i = 0; i < N; ++i) {
 
      // If the character is '0'
      if (S[i] == '0') {
 
        // If P[i-X] exists
        if (i - X >= 0) {
 
          // Set P[i-X] to '0'
          P[i - X] = '0';
        }
 
        // If P[i+X] exists
        if (i + X < N) {
 
          // Set P[i+X] to '0'
          P[i + X] = '0';
        }
      }
    }
 
    // Set flag to 1
    int flag = 1;
 
    // Loop to cross check
    // if P exists or not
    for (int i = 0; i < N; ++i) {
 
      // If the character is '1'
      if (S[i] == '1') {
 
        // If P[i-X] exists and
        // is equal to '1' or if
        // P[i+X] exists and
        // is equal to '1'
        if ((i - X >= 0 && P[i - X] == '1')
            || (i + X < N && P[i + X] == '1')) {
          continue;
        }
        else {
 
          // Set flag to 0
          flag = 0;
 
          // Output -1
          Console.Write(-1);
 
          // Break from the loop
          break;
        }
      }
    }
 
    // If flag is equal to 1
    if (flag == 1) {
 
      // Output string P
      string p = new string(P);
      Console.Write(p);
    }
  }
 
  // Driver Code
  public static void Main()
  {
    // Given input
    string S = "10011";
    int X = 2;
 
    // Function Call
    findString(S, X);
  }
}
 
// This code is contributed by Taranpreet

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find the original string P
    const findString = (S, X) => {
     
        // Stores the size of string S
        let N = S.length;
 
        // Each character of string
        // P is set to '1'
        let P = new Array(N).fill('1');
 
        // Loop to put zeroes at
        // the correct positions in P
        for (let i = 0; i < N; ++i) {
 
            // If the character is '0'
            if (S[i] == '0') {
 
                // If P[i-X] exists
                if (i - X >= 0) {
 
                    // Set P[i-X] to '0'
                    P[i - X] = '0';
                }
 
                // If P[i+X] exists
                if (i + X < N) {
 
                    // Set P[i+X] to '0'
                    P[i + X] = '0';
                }
            }
        }
 
        // Set flag to 1
        let flag = 1;
 
        // Loop to cross check
        // if P exists or not
        for (let i = 0; i < N; ++i) {
 
            // If the character is '1'
            if (S[i] == '1') {
 
                // If P[i-X] exists and
                // is equal to '1' or if
                // P[i+X] exists and
                // is equal to '1'
                if ((i - X >= 0
                    && P[i - X] == '1')
                    || (i + X < N
                        && P[i + X] == '1')) {
                    continue;
                }
                else {
 
                    // Set flag to 0
                    flag = 0;
 
                    // Output -1
                    document.write(-1);
 
                    // Break from the loop
                    break;
                }
            }
        }
 
        // If flag is equal to 1
        if (flag == 1) {
 
            // Output string P
            document.write(P.join(""));
        }
    }
 
    // Driver Code
 
    // Given input
    let S = "10011";
    let X = 2;
 
    // Function Call
    findString(S, X);
 
// This code is contributed by rakeshsahni
 
</script>
Producción: 

01100

 

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

Publicación traducida automáticamente

Artículo escrito por anusha00466 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 *