Given two strings, S and T where S is a normal string and T is a compressed string, the task is to determine if the compressed string T can be achieved by compressing the string S.
Note: A compression mechanism can arbitrarily delete X (X >= 0) characters and replace them with the deleted character count (X).
Examples:
Input: S = “HELLOWORLD” T=”H2L4L1″
Output: True
Explanation:
Replace index 1 to 2 in “HELLOWORLD” with count 2 -> “H2LOWORLD”
Replace index 4 to 7 in “HELLOWORLD” with count 4 -> “H2L4LD”
Replace index 9 in “HELLOWORLD” with count 1 -> “H2L4L1“
The resultant string is same as T. Hence String S can be compressed to T.Input: S = “DFS” T=”D1D”
Output: False
Explanation: We can clearly see that T is not a valid compressed string for S as compressed string T is ending with “D” which is not similar with the former string S.
Approach: The idea is to simply traverse the string and match the characters as follows:
- Compare the characters at corresponding indices in S and T,
- Similarly skip the count of indices in between two alphabets in T.
Illustration:
Consider S = “HELLOWORLD” T=”H2L4L1″
In compressed string, 2 is the integer between ‘H’ and ‘L’,so string S must has any two characters between ‘H’ and ‘L’, and it has (HELLOWORLD).
Then next integer is 4 between ‘L’ and ‘L’, then check whether String S has 4 characters or not, (HELLOWORLD)
And last integer is 1 after character ‘L’ and String also has 1 character(i.e ‘D’) after ‘L’. (HELLOWORLD)
So, this Compressed String is valid.
S = “HELLOWORLD” T=”H2L4L1“
Follow the below steps to solve the problem:
- Start Traversing S and T string until its length simultaneously.
- Check whether T[i] is number or not, if it is not a number then compare S[j] and T[i] if they are not equal then directly return 0 else continue and increment j by 1 .
- If T[i] is a number then increase the j to that number until we get numbers in T string .
- Increment i by 1 until length of T.
- If j is not equal to S of length then return 0.
- If all conditions are satisfied then return 1 at last.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Return 1 if char c is numberboolean isnum(char c) { return (c >= 48 && c <= 57); }// Function to check// If string is compressed or notint checkCompressed(string S, string T){ int i = 0, j = 0; // Iterate till S.length() // And T.length while (j < S.length() && i < T.length()) { if (isnum(T[i]) == false) { // If its not equal // Then return 0 if (S[j] != T[i]) { return 0; } j++; } else { int ans = T[i] - 48; // Iterate till we get number // In T string while (isnum(T[++i])) { ans *= 10; ans += T[i] - 48; } j += ans; i--; } i++; } // It j not equal to S string length // Then return 0 if (j != S.length()) { return 0; } return 1;}// Driver codeint main(){ string S = "HelloWorld"; string T = "H2l4l1"; cout << checkCompressed(S, T) << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG{// Return 1 if char c is numberstatic boolean isnum(char c) { return (c >= 48 && c <= 57); }// Function to check// If String is compressed or notstatic int checkCompressed(char[] S, char[] T){ int i = 0, j = 0; // Iterate till S.length() // And T.length while (j < S.length && i < T.length) { if (isnum(T[i]) == false) { // If its not equal // Then return 0 if (S[j] != T[i]) { return 0; } j++; } else { int ans = T[i] - 48; // Iterate till we get number // In T String while (i<T.length-1 && isnum(T[++i])) { ans *= 10; ans += T[i] - 48; } j += ans; i--; } i++; } // It j not equal to S String length // Then return 0 if (j != S.length) { return 0; } return 1;}// Driver codepublic static void main(String[] args){ String S = "HelloWorld"; String T = "H2l4l1"; System.out.print(checkCompressed(S.toCharArray(), T.toCharArray()) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# python3 code for the above approach:# Return 1 if char c is numberdef isnum(c): return ord(c) >= 48 and ord(c) <= 57# Function to check# If string is compressed or notdef checkCompressed(S, T): i, j = 0, 0 # Iterate till S.length() # And T.length while (j < len(S) and i < len(T)): if (isnum(T[i]) == False): # If its not equal # Then return 0 if (S[j] != T[i]): return 0 j += 1 else: ans = ord(T[i]) - 48 # Iterate till we get number # In T string i += 1 while (i < len(T) and isnum(T[i])): ans *= 10 ans += T[i] - 48 i += 1 j += ans i -= 1 i += 1 # It j not equal to S string length # Then return 0 if (j != len(S)): return 0 return 1# Driver codeif __name__ == "__main__": S = "HelloWorld" T = "H2l4l1" print(checkCompressed(S, T)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approach:using System;public class GFG{ // Return 1 if char c is number static boolean isnum(char c) { return (c >= 48 && c <= 57); } // Function to check // If String is compressed or not static int checkCompressed(char[] S, char[] T) { int i = 0, j = 0; // Iterate till S.length() // And T.length while (j < S.Length && i < T.Length) { if (isnum(T[i]) == false) { // If its not equal // Then return 0 if (S[j] != T[i]) { return 0; } j++; } else { int ans = T[i] - 48; // Iterate till we get number // In T String while (i<T.Length-1 && isnum(T[++i])) { ans *= 10; ans += T[i] - 48; } j += ans; i--; } i++; } // It j not equal to S String length // Then return 0 if (j != S.Length) { return 0; } return 1; } // Driver code static public void Main () { string S = "HelloWorld"; string T = "H2l4l1"; Console.Write(checkCompressed(S.ToCharArray(), T.ToCharArray()) ); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript Program of the above approach.// Return 1 if char c is numberfunction isnum(c) { return (c>= 48 && c <= 57); } // Function to check// If string is compressed or notfunction checkCompressed(S, T){ let i = 0, j = 0; // Iterate till S.length() // And T.length while (j < S.length && i < T.length) { if (isnum(T[i].charCodeAt()) == false) { // If its not equal // Then return 0 if (S[j] != T[i]) { return 0; } j++; } else { let ans = T[i].charCodeAt() - 48; // Iterate till we get number // In T string while (isnum(T[++i])) { ans *= 10; ans += T[i].charCodeAt() - 48; } j += ans; i--; } i++; } // It j not equal to S string length // Then return 0 if (j != S.length) { return 0; } return 1;} // Driver Code let S = "HelloWorld"; let T = "H2l4l1"; document.write( checkCompressed(S, T));// This code is contributed by code_hunt.</script> |
1
Time Complexity: O(max (|S|, |T|) )
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
