Minimum Unique Word Abbreviation Solution in C++

Explore More Solutions

Problem Description

Ah, the classic dilemma of abbreviating words! You know, like when you try to text your friend “See you later” and end up with “CUL8R” because typing is just too much effort. The Minimum Unique Word Abbreviation problem on LeetCode takes this concept to a whole new level.

Imagine you have a target word, and you want to create the shortest unique abbreviation for it that doesn’t clash with any words in a given dictionary. It’s like trying to find a unique username on a social media platform where every variation of your name is already taken. You want to stand out, but not in a way that makes people question your sanity!

In this problem, you need to find the shortest abbreviation for a target word that is not present in a dictionary of words of the same length. If you can’t find a unique abbreviation, just use the length of the target word as your abbreviation.

Code Solution


class Solution {
 public:
  string minAbbreviation(string target, vector& dictionary) {
    const int m = target.length();
    vector masks;

    for (const string& word : dictionary) {
      if (word.length() != m)
        continue;
      masks.push_back(getMask(target, word));
    }

    if (masks.empty())
      return to_string(m);

    vector abbrs;

    const int maxCand = pow(2, m);
    for (int cand = 0; cand < maxCand; ++cand)
      if (ranges::all_of(masks, [cand](int mask) { return cand & mask; }))
        abbrs.push_back(getAbbr(target, cand));

    string ans = target;

    for (const string& abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

 private:
  int getMask(const string& target, const string& word) {
    const int m = target.length();
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word[i] != target[i])
        mask |= 1 << m - 1 - i;
    return mask;
  }

  string getAbbr(const string& target, int cand) {
    const int m = target.length();
    string abbr;
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if (cand >> m - 1 - i & 1) {
        if (replacedCount > 0)
          abbr += to_string(replacedCount);
        abbr += target[i];
        replacedCount = 0;
      } else {
        ++replacedCount;
      }
    if (replacedCount > 0)
      abbr += to_string(replacedCount);
    return abbr;
  }

  int getAbbrLen(const string& abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (isalpha(abbr[j]))
        ++j;
      else
        while (j < abbr.length() && isdigit(abbr[j]))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
};

Approach Explanation

The code works by generating all possible abbreviations for the target word and checking them against the dictionary. It uses bit manipulation to create masks that represent which characters can be abbreviated. The algorithm then filters out any abbreviations that conflict with the words in the dictionary, ultimately returning the shortest valid abbreviation.

Mask Generation: For each word in the dictionary, a mask is created that indicates which characters differ from the target.
Candidate Generation: All possible combinations of abbreviations are generated using bit manipulation.
Validation: Each candidate abbreviation is checked against the masks to ensure it doesn't conflict with any dictionary words.
Selection: The shortest valid abbreviation is selected as the result.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2^m * m), where m is the length of the target word.
Space Complexity	O(n), where n is the number of words in the dictionary.

Real-World Example

Think of it like trying to create a unique username for your online gaming profile. You want something catchy, but every variation of your name is already taken. You might end up with something like "Gamer12345" when all you wanted was "GamerJoe." The Minimum Unique Word Abbreviation problem is just like that, but instead of usernames, we’re abbreviating words!