Minimum Unique Word Abbreviation Solution in Java

Quick Links

Problem Description

Ah, the classic dilemma of abbreviating words! You know, like when you try to text your friend “I’ll be there in 5 minutes” but end up typing “I’BTH5M” because, let’s face it, who has time for vowels? The Minimum Unique Word Abbreviation problem on LeetCode is a bit like that, but with a twist.

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.

For example, if your target is “apple” and your dictionary contains “blade” and “ample,” you can’t just abbreviate “apple” to “a3” because “ample” would also be abbreviated to “a3.” So, you need to get creative!

Code Solution


class Solution {
  public String minAbbreviation(String target, String[] dictionary) {
    final int m = target.length();
    List masks = new ArrayList<>();

    for (final String word : dictionary) {
      if (word.length() != m)
        continue;
      masks.add(getMask(target, word));
    }

    if (masks.isEmpty())
      return String.valueOf(m);

    List abbrs = new ArrayList<>();

    final int maxCand = (int) Math.pow(2, m);
    for (int i = 0; i < maxCand; ++i) {
      final int cand = i;
      if (masks.stream().allMatch(mask -> (cand & mask) > 0))
        abbrs.add(getAbbr(target, cand));
    }

    String ans = target;

    for (final String abbr : abbrs)
      if (getAbbrLen(abbr) < getAbbrLen(ans))
        ans = abbr;

    return ans;
  }

  private int getMask(final String target, final String word) {
    final int m = target.length();
    int mask = 0;
    for (int i = 0; i < m; ++i)
      if (word.charAt(i) != target.charAt(i))
        mask |= 1 << m - 1 - i;
    return mask;
  }

  String getAbbr(final String target, int cand) {
    final int m = target.length();
    StringBuilder sb = new StringBuilder();
    int replacedCount = 0;
    for (int i = 0; i < m; ++i)
      if ((cand >> m - 1 - i & 1) == 1) {
        if (replacedCount > 0)
          sb.append(replacedCount);
        sb.append(target.charAt(i));
        replacedCount = 0;
      } else {
        ++replacedCount;
      }
    if (replacedCount > 0)
      sb.append(replacedCount);
    return sb.toString();
  }

  int getAbbrLen(final String abbr) {
    int abbrLen = 0;
    int i = 0;
    int j = 0;
    while (i < abbr.length()) {
      if (Character.isAlphabetic(abbr.charAt(j)))
        ++j;
      else
        while (j < abbr.length() && Character.isDigit(abbr.charAt(j)))
          ++j;
      ++abbrLen;
      i = j;
    }
    return abbrLen;
  }
}

Approach Explanation

The code works by generating all possible abbreviations of the target word and checking them against the dictionary. It uses bit manipulation to create masks that represent the differences between the target and each word in the dictionary. The goal is to find the shortest abbreviation that is unique and does not conflict with any words in the dictionary.

Mask Generation: For each word in the dictionary, a mask is created that indicates which characters differ from the target.
Candidate Generation: All possible abbreviations are generated using bit manipulation.
Validation: Each candidate abbreviation is checked against the masks to ensure it is unique.
Selection: The shortest valid abbreviation is selected as the final answer.

Time and Space Complexity

Time Complexity: O(2^m * m), where m is the length of the target word. This is due to generating all possible abbreviations and checking them against the masks.

Space Complexity: O(n), where n is the number of words in the dictionary, as we store masks for each word.

Real-World Example

Think of it like trying to create a unique license plate for your car. You want something catchy, but it can't be the same as your neighbor's "CAR123" or your friend's "CAR124." You might end up with something like "C4U" (Car for You) that stands out and is unique. Similarly, the Minimum Unique Word Abbreviation problem helps you find that unique abbreviation for your target word.