Last Updated: 12 Mar, 2021
Generalized Abbreviation
Easy
Asked in company
You are given a string ‘STR’ consisting of English lowercase letters.
Your task is to find out all the generalised abbreviations of ‘STR’ and print an array/list of these abbreviations sorted in increasing order.
Note:
A string is said to be a generalised abbreviations string of ‘STR’ if we remove a substring of length ‘X’ from ‘STR’ and put the number ‘X’ at the place of the removed substring.
We can not remove two consecutive substrings or we can say generalised abbreviations will never have two consecutive numbers.
For example:
If ‘STR’ = “abc”,
Sorted generalized abbreviations of ‘STR’ are: [“1b1”, “1bc”, “2c”, “3”, “a1c”, “a2”, “ab1”, “abc”].
Input Format:
The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.
The first and the only line of each test case contains a string ‘STR’.
Output format:
For every test case, print all the generalised abbreviations of ‘STR’ separated by a single space.
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 <=10
1<= |STR| <= 20
Where |STR| is length of String 'STR'.
Time limit: 1 sec
Approaches
Approach: The idea is to use backtracking to generate all the generalised abbreviations of the given string.
Complete Algorithm:
- Make a recursive helper function which will receive 4 parameters that are: string ‘STR’, a string ‘TEMP’, an integer ‘INDEX’ and an integer ‘COUNT’.
- Declare a global array/list of strings say ‘ANS’.
- Base Case :
- If ‘INDEX’ is greater or equal than the size of ‘STR’ then do:
- Check the value of ‘COUNT’:
- If ‘COUNT’ is greater than 0 then append ‘COUNT’ into ‘TEMP’.
- Append the string ‘TEMP’ into ‘ANS’ and return.
- Check the value of ‘COUNT’:
- If ‘INDEX’ is greater or equal than the size of ‘STR’ then do:
- Recursive calls:
- We will make a recursive call without appending anything into ‘TEMP’ and just increasing both ‘INDEX’ and ‘COUNT’ by 1.
- We have two more cases here depending on the value of ‘COUNT’:
- If ‘COUNT’ is greater than 0:
- Append ‘COUNT’ in ‘TEMP’.
- Set ‘COUNT’ = 0.
- Increase ‘INDEX’ by 1.
- Make a recursive call with updated variables.
- If ‘COUNT’ is equal to 0:
- We will make a recursive call appending ‘STR[INDEX]’ into ‘TEMP’ and increasing both ‘INDEX’ and ‘COUNT’ by 1.
- If ‘COUNT’ is greater than 0:
- Return ‘ANS’: