Last Updated: 21 Apr, 2021
Ninja And Typing
Easy
Asked in companies
Ninja wants to print two strings in a text editor but his keyword allows typing lowercase English letters and backspace only.
Ninja type ‘N’ characters given by string ‘STR1’ to print the first string in the editor, and type ‘M’ characters given by string ‘STR2’ to print the second string. Both ‘STR1’ and ‘STR2’ have lowercase English characters and ‘#’ to denote backspace.
Your task is to return true if both strings that print on the text editor are equal otherwise return false. See the example for more clarity.
Note:
Backspace has no effect on empty text.
Example:
Consider ‘STR1’ = “ade##c#ba”, ‘STR2 = ‘a#ad#b#ba
Both ‘STR1’ and ‘STR2’ print the string “aba” on the text editor, thus we should return true.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two space-separated strings ‘STR1’ and ’STR2’ respectively.
Output Format:
For each test case, print “true” if both strings that print on the text editor are equals otherwise print “false”
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
2 <= N <= 10000
0 <= M <= 10000
Time limit: 1 sec
Approaches
We use a stack to simulate typing of each character. When ninja type backspace we pop the top character from the string otherwise we push the typed character on top of the string.
The steps are as follows:
- Create two empty stacks ‘STK1’, ‘STK2’.
- Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following :
- If STR1[i] = ‘#’ and ‘STK1’ is not empty, Pop the top element of ‘STK1’.
- If STR1[i] != ‘#’ Push STR1[i] at top of ‘STK1’.
- Run a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ do the following :
- If STR2[i] = ‘#’ and ‘STK2’ is not empty, Pop the top element of ‘STK2’.
- If STR2[i] != ‘#’ Push STR2[i] at top of ‘STK2’.
- Return true if both ‘STK1’ and ‘STK2’ are equal otherwise return false.
The basic idea is to Iterate through the string in reverse. If we see a backspace character, the next non-backspace character is skipped. If a character isn't skipped, it is part of the string that is printed on the text editor. We can use a two-pointer-based approach using it to check whether both printed strings will be the same or not.
The steps are as follows:
- Initialize four integer variables ‘P’:= ‘N’-1, ‘Q’:= ‘M’-1 and ‘SKIP1’: = 0, ‘SKIP2’: = 0.
- Run a loop where till ‘P’ >= 0 or ‘Q’ >= 0 and in each iteration do the following
- Run a loop till ‘P’ >= 0 and in each iteration do the following -:
- If STR1[‘P’] = ‘#’, then increment ‘SKIP1’ by 1 and decrement ‘P’ by 1.
- If ‘SKIP1’ > 0, then decrement both ‘SKIP1’ and ‘P’ by 1.
- Otherwise, break this inner loop.
- Run a loop till ‘P’ >= 0 and in each iteration do the following -:
- Run a loop till ‘Q’ >= 0 and in each iteration do the following -:
- If STR2[‘Q’] = ‘#’, then increment ‘SKIP2’ by 1 and decrement ‘Q’ by 1.
- If ‘SKIP2’ > 0, then decrement both ‘SKIP2’ and 'QP’ by 1.
- Otherwise, break this inner loop.
- If both ’P’ and ‘Q’ are not negative and ‘STR1[P]’ != ‘STR2[‘Q’] then return false.
- If either ‘P’ is negative or either ‘Q’ is negative, i.e we compare char with nothing then return false.
- Decrement ‘P’ and ‘Q’ by 1.
- Return true