Word Abbreviation

hard array string hash map trie

Problem

Replace each word with its shortest abbreviation a<num>b (first letter + count + last letter). If two words share an abbreviation, extend their prefix until distinct. If the abbreviation is not shorter than the word, keep the word.

Inputwords = ["like","god","internal","me","internet","interval","intension","face","intrusion"]

Output["l2e","god","internal","me","i6t","interval","inte4n","f2e","in6n"]

Group by same (len, first, last); raise prefix length within a group until unique.

words (comma-separated)

def word_abbrev(words):
    def abbr(w, p):
        if len(w) - p <= 3: return w
        return w[:p+1] + str(len(w) - p - 2) + w[-1]
    n = len(words); ans = [abbr(w, 0) for w in words]; prefix = [0] * n
    for i in range(n):
        while True:
            dups = [j for j in range(n) if j != i and ans[j] == ans[i]]
            if not dups: break
            for j in dups + [i]:
                prefix[j] += 1
                ans[j] = abbr(words[j], prefix[j])
    return ans

function wordsAbbreviation(words) {
  const abbr = (w, p) => w.length - p <= 3 ? w : w.slice(0, p + 1) + (w.length - p - 2) + w[w.length - 1];
  const n = words.length;
  const ans = words.map(w => abbr(w, 0));
  const prefix = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    while (true) {
      const dups = [];
      for (let j = 0; j < n; j++) if (j !== i && ans[j] === ans[i]) dups.push(j);
      if (!dups.length) break;
      for (const j of [...dups, i]) { prefix[j]++; ans[j] = abbr(words[j], prefix[j]); }
    }
  }
  return ans;
}

class Solution {
    String abbr(String w, int p) {
        if (w.length() - p <= 3) return w;
        return w.substring(0, p + 1) + (w.length() - p - 2) + w.charAt(w.length() - 1);
    }
    public List wordsAbbreviation(List words) {
        int n = words.size();
        String[] ans = new String[n]; int[] prefix = new int[n];
        for (int i = 0; i < n; i++) ans[i] = abbr(words.get(i), 0);
        for (int i = 0; i < n; i++) {
            while (true) {
                List dups = new ArrayList<>();
                for (int j = 0; j < n; j++) if (j != i && ans[j].equals(ans[i])) dups.add(j);
                if (dups.isEmpty()) break;
                dups.add(i);
                for (int j : dups) { prefix[j]++; ans[j] = abbr(words.get(j), prefix[j]); }
            }
        }
        return Arrays.asList(ans);
    }
}

string abbr(string w, int p) {
    if ((int)w.size() - p <= 3) return w;
    return w.substr(0, p + 1) + to_string((int)w.size() - p - 2) + w.back();
}
vector wordsAbbreviation(vector& words) {
    int n = words.size();
    vector ans(n); vector pre(n, 0);
    for (int i = 0; i < n; i++) ans[i] = abbr(words[i], 0);
    for (int i = 0; i < n; i++) {
        while (true) {
            vector dups;
            for (int j = 0; j < n; j++) if (j != i && ans[j] == ans[i]) dups.push_back(j);
            if (dups.empty()) break;
            dups.push_back(i);
            for (int j : dups) { pre[j]++; ans[j] = abbr(words[j], pre[j]); }
        }
    }
    return ans;
}

Explanation

Each word gets a short form like first-letter + count + last-letter (for example internal → i6l). The challenge is that two words can produce the same abbreviation, so we must grow the prefix just enough to make every abbreviation unique.

The helper abbr(w, p) keeps the first p+1 letters, then the count of the remaining middle letters, then the last letter. If shortening would not actually save characters (len(w) - p <= 3), it returns the whole word unchanged.

We start every word at prefix 0 (the shortest form). Then for each word i we look for any other word with the same current abbreviation. As long as such duplicates exist, we bump the prefix length of i and all its clashing partners and recompute their abbreviations.

Extending the prefix exposes one more distinguishing letter, so colliding words eventually drift apart. We repeat until word i stands alone, then move on; once every word is conflict-free, the array is the answer.

Example: internal, internet, interval all start as i6l/i6t/i6l-style clashes. Bumping prefixes turns them into things like internal, i6t, interval — each now unique and as short as possible.

Time: O(N · L²) Space: O(N · L)