Valid Word Abbreviations

Easy
0/40
Average time to solve is 10m
profile
Contributed by
19 upvotes
Asked in company
Facebook

Problem statement

You are given a string ‘STR’ consisting of English lowercase letters. You are also provided another string ‘ABBR’ consisting of lowercase letters and digits.

We say ‘ABBR’ matches ‘STR’ if it fulfils the following condition:

1) While matching, if we encounter a number ‘X’ in ‘ABBR’, then we have to skip ‘X’ characters in ‘STR’ and keep on matching.

For example: For ‘STR’ = “abc”, all valid matching ‘ABBR’ are: [“abc”, “1bc”, “1b1”, “2c”, “3”, “a1c”, “a2”, “ab1”].

Your task is to check whether ‘STR’ matches with the given ‘ABBR’ or not. Return TRUE if ‘STR’ matches with ‘ABBR’ else return FALSE.

For example :

If ‘STR’ = “hello” and ‘ABBR’= “1e2o”.
1. As ‘STR[0]’=’h’ but ‘ABBR[0]’=1 which means we can skip 1 character from ‘STR’ so continue matching.
2. ‘STR[1]’=’e’ and ‘ABBR[1]’=’e’ (matches) so continue matching.
3.‘STR[2]’=’l’ and ‘ABBR[2]’=2 which means we can skip 2 characters from ‘STR’ so continue matching.
4. We will not match the 3rd index as skipped in the earlier step.   
4.‘STR[4]’=’o’ and ‘ABBR[4]’=’o’ (matches). 
So we can say ‘STR’ matches with ‘ABBR’ and return TRUE.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.
First and the only line of each test case contains two single space-separated strings representing ‘STR’ and ‘ABBR’ respectively.

Output format :

For every test case, print ‘YES’ if ‘STR’ matches ‘ABBR’ else print ‘NO’.
The output of each test case is printed in a separate line.

Note :

You don’t have to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1<= T <=100
1<= |STR| and |ABBR| <=10^4

Time limit: 1 second

Sample input 1 :

1
abbreviations a11s

Sample output 1 :

YES

Explanation for sample output 1 :

For the given ‘STR’ = “abbreviations” and ‘ABBR’ = “a11s”, the character at the 0th index of both the strings matches, so we can continue matching for next indices.
For the next step, we encounter a number 11 in ‘ABBR’, which means we have to skip 11 characters from ‘STR’ and continue matching.
After skipping 11 indices, we move to the 12th index of ‘STR’. Now,  both ‘STR[12]’ = ‘s’ and ‘ABBR[3]’ = ‘s’ and match.
Finally, we reach the end of both strings. So we print YES as an answer.

Sample input 2 :

2
xyzzy 4
ninja 8inja

Sample output 2 :

NO
NO

Explanation for sample output 2 :

(i) For the first test case, ‘ABBR’ has only one digit that is 4 which means we have to skip 4 characters in ‘STR’ from the starting. And after skipping 4 characters, we are still left with one character in ‘STR’ and zero characters in ‘ABBR’. So, we can say that ‘STR’ does not match with ‘ABBR’.

(ii) For the second test case, the 0th index of ‘ABBR’ has a digit that is 8 which means we have to skip 8 characters in ‘STR’ from the starting. But the length of ‘STR’ is less than 8 which means we can not skip 8 characters. So, we can say that ‘STR’ does not match with ‘ABBR’.
Hint

Will converting the digits into a number help us?

Approaches (1)
Brute Force

The idea is very simple, we just need to match two strings with slight modifications as we may encounter digits in ‘ABBR’ string. If we  encounter more than 1 consecutive digits in ‘ABBR’, then we need to convert these digits into a number. After getting the number we just need to skip characters equal to that number in ‘STR’.

 

  • Let’s initialize two integer variables ‘IDX1’ =0 and ‘IDX2’ =0, these variables will be used to iterate over ‘STR’ and ‘ABBR’ respectively.
  • Run a loop, while ‘IDX1’ is less than the size of ‘STR’ and ‘IDX2’ is less than the size of ‘ABBR’ and do :
    • If ‘STR[IDX1]’ is equal to ‘ABBR[IDX2]’ then do :
      • Increase both IDX1 and IDX2 by 1.
    • Else :
      • If ‘ABBR[IDX2]’ is <= ‘0’ or > ‘9’ then do (it means it is a character but still does not match):
        • Return false.
      • Else :
        • Initialize an integer variable ‘COUNT’ = 0.
        • Run a loop while ‘ABBR[IDX2]’ is a digit  and do :
          • ‘COUNT’ = ‘COUNT’*10 + integer value of ‘ARRR[IDX2]’.
        • ‘IDX1’ = ‘IDX1’ + ‘COUNT’.
  • If ‘IDX1’ is equal to the length of ‘STR’ and ‘IDX2’ is equal to the length of ‘ABBR’ then return TRUE else return FALSE.
Time Complexity

O(N), where N is the size of string ‘STR’.

 

In the worst case when ‘ABBR’ has no digits and it is also equal to ‘STR’, we will traverse the whole ‘STR’ and match it against ‘ABBR’ resulting in a time complexity of O(N).

Space Complexity

O(1).

 

As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Valid Word Abbreviations
Full screen
Console