Valid Compressed String
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 = “w3wiki”, 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 code int main() { string S = "w3wiki" , 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 = "w3wiki" , 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 code S = "w3wiki" 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 code let S = "w3wiki" ; let T = "G7G3S" ; // Function call let 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 code public static void Main( string [] args) { string S = "w3wiki" , 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