Compruebe si una string se puede vaciar eliminando todas las subsecuencias de la forma «10»

Dada una string binaria str , la tarea es verificar si la string se puede vaciar eliminando todas las subsecuencias de la forma «10»
 

Ejemplos :

Entrada: str = “11011000”
Salida: Sí
Explicación: Se requieren los siguientes pasos para vaciar la string dada “11011000” → “111000” → “1100” → “10” → “”

Entrada : 101001
Salida : No

Enfoque: siga los pasos a continuación para resolver el problema:

1. Atraviese la string y almacene todos los 1 en una pila .
2. Si str[i] = 1 , guárdelo en la pila.
3. Si str[i] = 0 y la pila no está vacía , extraiga el carácter en la parte superior de la pila .
4. De lo contrario, devuelve falso .
5. Si la pila está vacía, devuelve verdadero .
6. 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 find if string
// is reducible to NULL
bool isReducible(string str)
{
    // Length of string
    int N = str.size();
 
    // Stack to store all 1s
    stack<char> s;
 
    // Iterate over the characters
    // of the string
    for (int i = 0; i < N; i++) {
 
        // If current character is 1
        if (str[i] == '1')
 
            // Push it into the stack
            s.push(str[i]);
 
        else if (!s.empty())
 
            // Pop from the stack
            s.pop();
 
        else
            // If the stack is empty
            return false;
    }
 
    return s.empty();
}
 
// Driver Code
int main()
{
    string str = "11011000";
 
    if (isReducible(str))
        cout << "Yes";
 
    else
        cout << "No";
    return 0;
}

// Java program for
// the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to find if string
  // is reducible to NULL
  static boolean isReducible(String str)
  {
 
    // Length of string
    int N = str.length();
 
    // Stack to store all 1s
    ArrayList<Character> s = new ArrayList<Character>();
 
    // Iterate over the characters
    // of the string
    for (int i = 0; i < N; i++)
    {
 
      // If current character is 1
      if (str.charAt(i) == '1')
 
        // Push it into the stack
        s.add(str.charAt(i));
      else if (s.size() > 0)
 
        // Pop from the stack
        s.remove(s.size() - 1);
 
      else
 
        // If the stack is empty
        return false;
    }
 
    if(s.size() == 0)
    {
      return true;
    }
    else{
      return false;
    }
 
  }
 
  // Driver code
  public static void main (String[] args)
  {
    String str = "11011000";
    if (isReducible(str))
    {
      System.out.println("Yes");
    }
    else
    {
      System.out.println("No");
    }
  }
}
 
// This code is contributed by avanitrachhadiya2155

# Python3 program for the above approach
 
# Function to find if string
# is reducible to NULL
def isReducible(Str) :
 
    # Length of string
    N = len(Str)
     
    # Stack to store all 1s
    s = []
     
    # Iterate over the characters
    # of the string
    for i in range(N) :
     
      # If current character is 1
      if (Str[i] == '1') :
     
        # Push it into the stack
        s.append(Str[i])
     
      elif(len(s) > 0) :
     
        # Pop from the stack
        del s[len(s) - 1]
     
      else :
        # If the stack is empty
        return False
     
    if(len(s) == 0) :
      return True
       
    else :
      return False
       
      # Driver code
Str = "11011000"
  
if (isReducible(Str)) :
  print("Yes")
 
else :
  print("No")
   
  # This code is contributed by divyeshrabadiya07.

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find if string
  // is reducible to NULL
  static bool isReducible(string str)
  {
    // Length of string
    int N = str.Length;
 
    // Stack to store all 1s
    List<char> s = new List<char>();
 
    // Iterate over the characters
    // of the string
    for (int i = 0; i < N; i++) {
 
      // If current character is 1
      if (str[i] == '1')
 
        // Push it into the stack
        s.Add(str[i]);
 
      else if (s.Count > 0)
 
        // Pop from the stack
        s.RemoveAt(s.Count - 1);
 
      else
        // If the stack is empty
        return false;
    }
 
    if(s.Count == 0)
    {
      return true;
    }
    else{
      return false;
    }
  }
 
  // Driver code
  static void Main()
  {
    string str = "11011000";
 
    if (isReducible(str))
      Console.WriteLine("Yes");
 
    else
      Console.WriteLine("No");
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for
    // the above approach
     
    // Function to find if string
    // is reducible to NULL
    function isReducible(str)
    {
      // Length of string
      let N = str.length;
 
      // Stack to store all 1s
      let s = [];
 
      // Iterate over the characters
      // of the string
      for (let i = 0; i < N; i++) {
 
        // If current character is 1
        if (str[i] == '1')
 
          // Push it into the stack
          s.push(str[i]);
 
        else if (s.length > 0)
 
          // Pop from the stack
          s.pop();
 
        else
          // If the stack is empty
          return false;
      }
 
      if(s.length == 0)
      {
        return true;
      }
      else{
        return false;
      }
    }
       
    let str = "11011000";
  
    if (isReducible(str))
      document.write("Yes");
  
    else
      document.write("No");
       
      // This code is contributed by suresh07.
</script>

Yes

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