Last Updated: 29 Oct, 2021
Faulty Keyboard
Easy
Asked in companies
Ninja has an old keyboard, which is now a piece of junk, but Ninja still loves it.
There is a major problem with the keyboard, pressing a single key can type the same character multiple times. This sometimes results in incorrect text being typed.
You are given two strings ‘Expected’ and ‘Typed’, you need to tell if the actual text was typed correctly or not. The text is typed correctly if some characters were long pressed (typed multiple times) while typing the ‘Expected’ text. Print “true” if the actual text was typed correctly, else print “false”.
For Example :
If Typed = “aaabcc” and Expected = “abc”
Then, while trying to type “abc” one might long press ‘a’ and that would result in typing three consecutive a’s. This if followed by correctly pressing ‘b’ once and in the end he might long press ‘c’ resulting in typing it twice, the resulting text typed in this case is equal to “aaabcc” and therefore we will return “true”.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a string ‘Expected’ that denotes the original text that was to be typed.
The second line of each test case contains a string ‘Typed’ that denotes the text that was actually typed.
Output Format :
For each test case, print the “true” if the text was typed correctly, else print “false”.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ |Expected| ≤ 5000
1 ≤ |Typed| ≤ 5000
Both the strings consist of lowercase English alphabets
Time limit: 1 sec
Approaches
Initialize two pointers to point to the beginning of each string. Run a while loop, check if both the pointers point to the same characters or not, in case they point to different characters then return “False” as this is the case when it is not possible to match the strings as a different character is typed or the order in which characters were typed is different. If the current characters pointed by both the pointers match then run a while loop to take increase the pointer pointing the ‘Typed’ text if needed to consider the condition of using the faulty keyboard. Break the outer while loop if both the pointers point to the end of their respective strings and return “True” as this will denote that we have matched the condition of the faulty keyboard. In case only one of the pointers points to the end of its string then return “False” as this is the case when we might have pressed some extra incorrect keys in the end or might have pressed fewer keys than that were actually to be pressed for typing the text.
The steps are as follows :
- Initialize two pointers ‘pt1’ and ‘pt2’ and set their values equal to 0. We will use these pointers to iterate through the strings, ‘pt1’ will iterate through the ‘Expected’ string and ‘pt2’ will iterate through the ‘Typed’ string.
- Run a while loop, inside the loop check:
- If both the pointers point to the ends of their respective strings, if found then return “True”
- If not, then check if one of them points to the end of its string, if found then return “False”.
- Else check if both the pointers point to the equal characters or not, if they point to different characters then return “False”. If it points to equal characters then, increment the value of both the pointer by one unit.
- Now run an inner while loop to take into account the condition of the faulty keyboard, run this while loop till ‘pt2’ doesn’t point to the end and till the characters at position Typed[pt2] and Typed[pt2 - 1] are equal.
- Increment the value of ‘pt2’ inside this while loop till the above-mentioned conditions are true.