Verifique si la string binaria dada sigue la condición dada o no

Dada la string binaria str , la tarea es verificar si la string dada sigue la siguiente condición o no: 
 

• La string comienza con un ‘1’ .
• Cada ‘1’ va seguido de una string vacía ( «» ), ‘1’ o «00» .
• Cada «00» va seguido de una string vacía ( «» ), ‘1’ .

Si la string dada sigue los criterios anteriores, imprima «String válida»; de lo contrario, imprima «String no válida» .
Ejemplos: 
 

Entrada: str = “1000” 
Salida: Falso 
Explicación: 
La string dada comienza con “1” y tiene “00” seguido por el “1” que no es el criterio dado. 
Por lo tanto, la string dada es «String no válida».
Entrada: str = “1111” 
Salida: Verdadero 
Explicación: 
La string dada comienza con 1 y tiene 1 seguido de todos los 1. 
Por lo tanto, la string dada es «String válida». 
 

Enfoque: La idea es usar Recursión . A continuación se muestran los pasos: 
 

1. Compruebe si el carácter 0 ^es ‘ 1′ o no. Si no es ‘1’ , devuelve falso ya que la string no sigue la condición 1.
2. Para verificar que la string cumpla con la segunda condición, llame recursivamente a una string que comience desde el primer índice usando la función substr() en C++.
3. Para verificar que la string cumpla con la tercera condición, primero, debemos verificar si la longitud de la string es mayor que 2 o no. En caso afirmativo, compruebe si ‘0’ está presente en el primer y segundo índice. En caso afirmativo, llame recursivamente a la string que comienza en el tercer índice.
4. En cualquier llamada recursiva, si la string está vacía, entonces hemos recorrido la string completa que cumple todas las condiciones dadas e imprimimos «String válida» .
5. En cualquier llamada recursiva, si la condición dada no satisface, detenga esa recursividad e imprima «String no válida» .

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 if the
// string follows rules or not
bool checkrules(string s)
{
    if (s.length() == 0)
        return true;
 
    // Check for the first condition
    if (s[0] != '1')
        return false;
 
    // Check for the third condition
    if (s.length() > 2) {
        if (s[1] == '0' && s[2] == '0')
            return checkrules(s.substr(3));
    }
 
    // Check for the second condition
    return checkrules(s.substr(1));
}
 
// Driver Code
int main()
{
    // Given String str
    string str = "1111";
 
    // Function Call
    if (checkrules(str)) {
        cout << "Valid String";
    }
    else {
        cout << "Invalid String";
    }
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check if the
// String follows rules or not
static boolean checkrules(String s)
{
    if (s.length() == 0)
        return true;
 
    // Check for the first condition
    if (s.charAt(0) != '1')
        return false;
 
    // Check for the third condition
    if (s.length() > 2)
    {
        if (s.charAt(1) == '0' &&
            s.charAt(2) == '0')
            return checkrules(s.substring(3));
    }
 
    // Check for the second condition
    return checkrules(s.substring(1));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given String str
    String str = "1111";
 
    // Function call
    if (checkrules(str))
    {
        System.out.print("Valid String");
    }
    else
    {
        System.out.print("Invalid String");
    }
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program for the above approach
 
# Function to check if the
# string follows rules or not
def checkrules(s):
     
    if len(s) == 0:
        return True
         
    # Check for the first condition
    if s[0] != '1':
        return False
         
    # Check for the third condition
    if len(s) > 2:
        if s[1] == '0' and s[2] == '0':
            return checkrules(s[3:])
             
    # Check for the second condition
    return checkrules(s[1:])
     
# Driver code
if __name__ == '__main__':
     
    # Given string
    s = '1111'
     
    # Function call
    if checkrules(s):
        print('valid string')
    else:
        print('invalid string')
         
# This code is contributed by virusbuddah_

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if the
// String follows rules or not
static bool checkrules(String s)
{
    if (s.Length == 0)
        return true;
 
    // Check for the first condition
    if (s[0] != '1')
        return false;
 
    // Check for the third condition
    if (s.Length > 2)
    {
        if (s[1] == '0' &&
            s[2] == '0')
            return checkrules(s.Substring(3));
    }
 
    // Check for the second condition
    return checkrules(s.Substring(1));
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given String str
    String str = "1111";
 
    // Function call
    if (checkrules(str))
    {
        Console.Write("Valid String");
    }
    else
    {
        Console.Write("Invalid String");
    }
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript program for the above approach
 
// Function to check if the
// string follows rules or not
function checkrules(s)
{
    if (s.length == 0)
        return true;
 
    // Check for the first condition
    if (s[0] != '1')
        return false;
 
    // Check for the third condition
    if (s.length > 2) {
        if (s[1] == '0' && s[2] == '0')
            return checkrules(s.substring(3));
    }
 
    // Check for the second condition
    return checkrules(s.substring(1));
}
 
// Driver Code
// Given String str
var str = "1111";
// Function Call
if (checkrules(str)) {
    document.write( "Valid String");
}
else {
    document.write( "Invalid String");
}
 
</script>

Valid String

Complejidad de tiempo: O(N) , donde N es la longitud de la string. 
Espacio Auxiliar: O(1) .