Word Abbreviation Solution in Java

Explore Other Solutions

Problem Description

Welcome to the world of word abbreviations, where we take long, cumbersome words and turn them into something that sounds like a secret code! Imagine you’re at a party, and you want to impress everyone with your linguistic prowess, but you don’t want to waste time saying “extraordinarily” when you can just say “ex3y.”

In this LeetCode problem, you’re tasked with creating abbreviations for a list of words. The catch? If two words end up with the same abbreviation, you need to adjust them until they’re unique. It’s like trying to find a unique username on social media—everyone wants to be “coolguy,” but you might have to settle for “coolguy123” instead.

Code Solution


class Solution {
  public List wordsAbbreviation(List words) {
    final int n = words.size();
    List ans = new ArrayList<>();
    int[] prefix = new int[n];

    for (int i = 0; i < n; ++i)
      ans.add(getAbbrev(words.get(i), 0));

    for (int i = 0; i < n; ++i)
      while (true) {
        List dupeIndices = new ArrayList<>();
        for (int j = i + 1; j < n; ++j)
          if (ans.get(i).equals(ans.get(j)))
            dupeIndices.add(j);
        if (dupeIndices.isEmpty())
          break;
        dupeIndices.add(i);
        for (final int dupeIndex : dupeIndices)
          ans.set(dupeIndex, getAbbrev(words.get(dupeIndex), ++prefix[dupeIndex]));
      }

    return ans;
  }

  private String getAbbrev(final String s, int prefixIndex) {
    final int n = s.length();
    final int num = n - (prefixIndex + 1) - 1;
    final int numLength = num < 10 ? 1 : num < 100 ? 2 : 3;
    final int abbrevLength = (prefixIndex + 1) + numLength + 1;
    if (abbrevLength >= n)
      return s;
    return s.substring(0, prefixIndex + 1) + num + s.charAt(n - 1);
  }
}

Approach

The approach taken in this solution is quite systematic. First, we initialize a list to hold the abbreviations and an array to track the prefixes for each word. We generate the initial abbreviation for each word and then check for duplicates. If duplicates are found, we increment the prefix for those words and generate new abbreviations until all are unique. It’s like a game of musical chairs, but with words!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²) in the worst case, where n is the number of words.
Space Complexity	O(n) for storing the abbreviations and the prefix array.

Real-World Example

Imagine you’re at a tech conference, and everyone is introducing themselves with their full names. “Hello, I’m Alexander the Great,” “Hi, I’m Benjamin Franklin,” and so on. It’s a mouthful! But if they abbreviate to “Alex3t” and “Ben9n,” it’s much easier to remember. This problem is all about making communication more efficient, just like how we abbreviate our friends’ names to avoid saying their full names every time.