# Valid Word Abbreviations

Posted: 18 Feb, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### 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”].
``````

#### For example :

``````If ‘STR’ = “hello” and ‘ABBR’= “1e2o”.
1. As ‘STR’=’h’ but ‘ABBR’=1 which means we can skip 1 character from ‘STR’ so continue matching.
2. ‘STR’=’e’ and ‘ABBR’=’e’ (matches) so continue matching.
3.‘STR’=’l’ and ‘ABBR’=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’=’o’ and ‘ABBR’=’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.