Abbreviation Generator
Solve a hard-level problem of creating unique abbreviations of input strings using tries.
Problem statement
In this problem, you'll be developing an abbreviation generator. The initial abbreviation for a string is the first character, then the number of characters in between, followed by the last character.
When given a list of words, if more than one word shares the same abbreviation, perform the following operation: increase the prefix (characters in the first part) of each of their abbreviations by 1.
For example, say you start with the words ["abcdef", "abndef"], both initially abbreviated as "a4f". Then, a sequence of operations would be ["a4f","a4f"] -> ["ab3f","ab3f"] -> ["abc2f","abn2f"].
This operation is repeated until every abbreviation is unique. In the end, if an abbreviation does not shorten a word, then keep it as the original word.
Given an array of distinct string words, generate and return the minimal possible and unique abbreviations for every word.
Example 1
Sample input
words: ["interact", "internet", "intranet", "and", "incident"]
Sample output
["interact", "internet", "intr3t","and", "inc4t"]
Explanation
The list below describes the abbreviation generation procedure step-by-step:["interact", "internet", "intranet", "and", "incident"]
["i6t", "i6t", "i6t", "a1d", "i6t"]
["in5t", "in5t", "in5t", "and", "in5t"]
["int4t", "int4t", "int4t", "and", "inc4t"]
["inte3t", "inte3t", "intr3t", "and", "inc4t"]
["inter2t", "inter2t", "intr3t", "and", "inc4t"]
["intera1t", "intern1t", "intr3t", "and", "inc4t"]
["interact", "internet", "intr3t", "and", "inc4t"]
Example 2
Sample input
words: ["bb","bbb"]
Sample output
["bb","bbb"]
Explanation
The list below describes the abbreviation generation procedure step-by-step:["bb", "bbb"]
["bb", "b1b"]
["bb", "bbb"]
Try it yourself
Try to solve the problem yourself before reading the solution.
#include <iostream>#include <vector>using namespace std;vector<string> wordAbbreviations(vector<string> words) {// your code goes herevector<string> answer;return answer;}
Intuition
From the problem description, we can infer that words having the same length and the same first and last letters can be grouped together, as they would have the same initial abbreviations. Next, we need to identify a method to resolve the duplicates in each group.
We'll start by choosing the shortest abbreviation for each word. Then, while we have duplicates, we can keep increasing the length of all the abbreviations until all the duplicates are resolved.
Let's try to understand the procedure better with the help of an example. Assume we have the strings "aabaaa", "aacaaa", "aacdaa" as input. We start with abbreviations "a4a", "a4a", "a4a". Since these are duplicates, we change them to "aa3a", "aa3a", and "aa3a". But they're still duplicates, so we modify them to "aab2a", "aac2a", and "aac2a".
The last two are still duplicates, so we extend them to "aacaaa", "aacdaa". So now all the words have different abbreviations: "aab2a", "aacaaa", and "aacaaa", respectively.
Once we've segregated the words into groups, the next step is to resolve duplicates among the groups and identify unique abbreviations. To resolve conflicts in a group, we build a trie for all the words in the group. We can store information about the number of words having a particular prefix in a trie node, as we discussed in this lesson. ...