Compruebe si una string se puede dividir en substrings que comienzan con N seguidas de N caracteres

Dada una string str , la tarea es verificar si se puede dividir en substrings de modo que cada substring comience con un valor numérico seguido de una cantidad de caracteres representados por ese número entero.

Ejemplos:

Entrada: str = “4g12y6hunter”
Salida: Sí
Explicación: Las
substrings “4g12y” y “6hunter” cumplen la condición dada

Entrada: str = “31ba2a”
Salida: No
Explicación:
La string completa no se puede dividir en substrings de los tipos deseados

Acercarse:

Siga los pasos a continuación para resolver el problema:
• Verifique las condiciones cuando una división no es posible:
• Si la string dada no comienza con un número.
• Si el número entero, al comienzo de una substring, es mayor que el número total de caracteres subsiguientes en la substring restante.
• Si las dos condiciones anteriores no se cumplen, definitivamente es posible una respuesta. Por lo tanto, encuentre las substrings recursivamente.

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 the given // can be split into desired // substrings bool helper(string& s, int pos) {     // Length of the string     int len = s.size();        if (pos >= len)         return true;        if (!isdigit(s[pos]))         return false;        int num = 0;        // Traverse the string     for (int i = pos; i < len; i++) {            // Extract the digit         num = num * 10 + s[pos] - '0';            // Check if the extracted number         // does not exceed the remaining         // length         if (i + 1 + num > len)             return false;            // Check for the remaining         // string         if (helper(s, i + 1 + num))             return true;     }        // If generating desired     // substrings is not possible     return false; }    // Driver Code int main() {     string s = "123abc4db1c";     if (helper(s, 0))         cout << "Yes";     else         cout << "No"; }

Java

// Java program to implement the  // above approach  import java.util.*;    class GFG{        // Function to check if the given  // can be split into desired  // substrings  public static boolean helper(String s, int pos)  {             // Length of the string      int len = s.length();             if (pos >= len)          return true;      if (!Character.isDigit(s.charAt(pos)))         return false;             int num = 0;             // Traverse the string      for(int i = pos; i < len; i++)     {                   // Extract the digit         num = num * 10 + s.charAt(pos) - '0';                   // Check if the extracted number         // does not exceed the remaining         // length         if (i + 1 + num > len)             return false;                   // Check for the remaining         // string         if (helper(s, i + 1 + num))             return true;      }             // If generating desired      // substrings is not possible      return false;  }     // Driver code public static void main (String[] args) {     String s = "123abc4db1c";             if (helper(s, 0))          System.out.print("Yes");     else         System.out.print("No"); } }    // This code is contributed by divyeshrabadiya07

Python3

# Python3 program to implement the # above approach    # Function to check if the given # can be split into desired # substrings def helper(s, pos):            # Length of the string     size = len(s)        if(pos >= size):         return True        if(s[pos].isdigit() == False):         return False        num = 0        # Traverse the string     for i in range(pos, size):                    # Extract the digit         num = num * 10 + ord(s[pos]) - 48            # Check if the extracted number         # does not exceed the remaining         # length         if (i + 1 + num > size):             return False            # Check for the remaining         # string         if (helper(s, i + 1 + num)):             return True        # If generating desired     # substrings is not possible     return False    # Driver Code s = "123abc4db1c";    if (helper(s, 0)):     print("Yes") else:     print("No")    # This code is contributed by Sanjit_Prasad

C#

// C# program to implement the  // above approach  using System;    class GFG{         // Function to check if the given  // can be split into desired  // substrings  public static bool helper(String s, int pos)  {              // Length of the string      int len = s.Length;              if (pos >= len)          return true;      if (!char.IsDigit(s[pos]))         return false;              int num = 0;              // Traverse the string      for(int i = pos; i < len; i++)     {                    // Extract the digit         num = num * 10 + s[pos] - '0';                    // Check if the extracted number         // does not exceed the remaining         // length         if (i + 1 + num > len)             return false;                    // Check for the remaining         // string         if (helper(s, i + 1 + num))             return true;      }              // If generating desired      // substrings is not possible      return false;  }      // Driver code public static void Main(String[] args) {     String s = "123abc4db1c";              if (helper(s, 0))          Console.Write("Yes");     else         Console.Write("No"); } }    // This code is contributed by amal kumar choubey

Producción:

Yes


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