Valid Word Abbreviations

Posted: 18 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem