Given a string str, the task is to check if it can be split into substrings such that each substring starts with a numeric value followed by a number of characters represented by that numeric integer. Examples:
Input: str = “4g12y6hunter” Output: Yes Explanation: Substrings “4g12y” and “6hunter” satisfy the given condition Input: str = “31ba2a” Output: No Explanation: The entire string cannot be split into substrings of desired types
Approach:
- Check for the conditions when a split is not possible:
- If the given string does not start with a number.
- If the integer, in the beginning of a substring, is greater than the total number of succeeding characters in the remaining substring.
- If the above two condition are not satisfied, an answer is definitely possible. Hence find the substrings recursively.
Below is the implementation of the above approach:
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// substringsbool 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 Codeint main(){ string s = "123abc4db1c"; if (helper(s, 0)) cout << "Yes"; else cout << "No";} |
Java
// Java program to implement the// above approachimport java.util.*;class GFG{ // Function to check if the given// can be split into desired// substringspublic 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 codepublic 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# substringsdef 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 Codes = "123abc4db1c";if (helper(s, 0)): print("Yes")else: print("No")# This code is contributed by Sanjit_Prasad |
C#
// C# program to implement the// above approachusing System;class GFG{ // Function to check if the given// can be split into desired// substringspublic 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 codepublic 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 |
Javascript
// JavaScript program to implement the above approach// Function to check if the given// can be split into desired// substringsfunction helper(s, pos) { // Length of the string let size = s.length; if (pos >= size) { return true; } if (!/^\d+$/.test(s[pos])) { return false; } let num = 0; // Traverse the string for (let i = pos; i < size; i++) { // Extract the digit num = num * 10 + parseInt(s[i]); // 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 Codelet s = "123abc4db1c";if (helper(s, 0)) { console.log("Yes");} else { console.log("No");}//contributed by adityasha4x71 |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
