A special compression mechanism can arbitrarily delete 0 or more characters and replace them with the deleted character count.
Given two strings, S and T where S is a normal string and T is a compressed string, determine if the compressed string T is valid for the plaintext string S.
Examples:
Input: S = “GEEKSFORGEEKS”, T = “G7G3S”
Output: 1
Explanation: We can clearly see that T is a valid compressed string for S.Input: S = “DFS”, T = “D1D”
Output: 0
Explanation: T is not a valid compressed string.
Approach: To solve the problem follow the below idea:
Idea is to traverse through the string T using variable i and take a variable j and initialize it to 0, if we find an integer in string T, increase the j pointer by that integer and then compare S[j] and T[i]. If at any point, it doesn’t match, the compressed String isn’t valid.
Below are the steps for the above approach:
- Initialize 3 variables flag = 1, j = 0, and n = 0.
- Run a loop from i = 0 to i < length of t.
- Check if t[i] is a digit, retrieve the digit, and decrement j by 1.
- Else update j += n and check if t[i] != s[j], mark the flag = 0, and break the loop. Reset n to 0 and increment j by 1.
- When the loop ends, Increment j by n.
- Check if j != s.length(), and mark the flag = 0.
- Check if flag == 1, return 1, else return 0.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int checkCompressed(string s, string t){ int n = 0; int flag = 1; int j = 0; for (int i = 0; i < t.length(); i++) { if (t[i] >= '0' && t[i] <= '9') { n *= 10; if (n > 100000) return 0; n += t[i] - '0'; j--; } else { j += n; if (t[i] != s[j]) { flag = 0; break; } n = 0; } j++; } j += n; if (j != s.length()) flag = 0; if (flag) return 1; else return 0;}// Drivers codeint main(){ string S = "GEEKSFORGEEKS", T = "G7G3S"; int ans = checkCompressed(S, T); cout << ans;} |
Java
// Java code for the above approach:import java.io.*;class GFG { // Function to check the compressed string. static int checkCompressed(String s, String t) { int n = 0; boolean flag = true; int j = 0; for (int i = 0; i < t.length(); i++) { if (t.charAt(i) >= '0' && t.charAt(i) <= '9') { n *= 10; if (n > 100000) return 0; n += (int)t.charAt(i) - '0'; j--; } else { j += n; if (t.charAt(i) != s.charAt(j)) { flag = false; break; } n = 0; } j++; } j += n; if (j != s.length()) flag = false; if (flag) return 1; else return 0; } public static void main(String[] args) { String S = "GEEKSFORGEEKS", T = "G7G3S"; int ans = checkCompressed(S, T); System.out.println(ans); }}// This code is contributed by karthik. |
Python3
# Python3 code for the above approach:def checkCompressed(s, t): n = 0 flag = 1 j = 0 for i in range(len(t)): if t[i].isdigit(): n *= 10 if n > 100000: return 0 n += int(t[i]) j -= 1 else: j += n if t[i] != s[j]: flag = 0 break n = 0 j += 1 j += n if j != len(s): flag = 0 if flag: return 1 else: return 0# Driver codeS = "GEEKSFORGEEKS"T = "G7G3S"ans = checkCompressed(S, T)print(ans)# This code is contributed by Prajwal Kandekar |
Javascript
// JavaScript code for the above approach// Function to check the compressed string.function checkCompressed(s, t) { let n = 0; let flag = true; let j = 0; for (let i = 0; i < t.length; i++) { if (t[i] >= '0' && t[i] <= '9') { n *= 10; if (n > 100000) return 0; n += parseInt(t[i]); j--; } else { j += n; if (t[i] != s[j]) { flag = false; break; } n = 0; } j++; } j += n; if (j !== s.length) flag = false; if (flag) return 1; else return 0;}// Driver codelet S = "GEEKSFORGEEKS";let T = "G7G3S";// Function calllet ans = checkCompressed(S, T);console.log(ans); |
C#
using System;public class GFG{ // Function to check the compressed string.static int checkCompressed(string s, string t) { int n = 0; bool flag = true; int j = 0; for (int i = 0; i < t.Length; i++) { if (t[i] >= '0' && t[i] <= '9') { n *= 10; if (n > 100000) return 0; n += (int)t[i] - '0'; j--; } else { j += n; if (t[i] != s[j]) { flag = false; break; } n = 0; } j++; } j += n; if (j != s.Length) flag = false; if (flag) return 1; else return 0;} // Driver codepublic static void Main(string[] args) { string S = "GEEKSFORGEEKS", T = "G7G3S"; int ans = checkCompressed(S, T); Console.WriteLine(ans);} } |
1
Time Complexity: O(T) //In the above-given approach, there is one loop for iterating over string which takes O(T) time in worst case. Therefore, the time complexity for this approach will be O(T).
Auxiliary Space: O(1) //since no extra array or data structure is used so the space taken by the algorithm is constant
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
