Unique Word Abbreviation - Practice Coding Problems

Unique Word Abbreviation - Problem

The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.

For example:

dog → d1g because there is one letter between the first letter 'd' and the last letter 'g'.
internationalization → i18n because there are 18 letters between the first letter 'i' and the last letter 'n'.
it → it because any word with only two characters is an abbreviation of itself.

Implement the ValidWordAbbr class:

ValidWordAbbr(String[] dictionary) Initializes the object with a dictionary of words.
boolean isUnique(string word) Returns true if either of the following conditions are met (otherwise returns false):

There is no word in dictionary whose abbreviation is equal to word's abbreviation.
For any word in dictionary whose abbreviation is equal to word's abbreviation, that word and word are the same.

Input & Output

Example 1 — Basic Dictionary Operations

$ Input: dictionary = ["deer", "door", "cake", "card"], operations = ["dear", "cart", "cane", "make"]

› Output: [false, true, false, true]

💡 Note: dear→d2r conflicts with deer and door. cart→c2t is unique. cane→c2e conflicts with cake. make→m2e is unique.

Example 2 — Word Matches Dictionary

$ Input: dictionary = ["hello", "world"], operations = ["hello", "hallo"]

› Output: [true, false]

💡 Note: hello is in dictionary with abbreviation h3o, so it's unique to itself. hallo→h3o conflicts with hello.

Example 3 — Short Words

$ Input: dictionary = ["it", "is"], operations = ["it", "at"]

› Output: [true, true]

💡 Note: Short words are their own abbreviations: it→it, is→is, at→at. All unique.

Constraints

1 ≤ dictionary.length ≤ 3 × 10⁴
1 ≤ dictionary[i].length ≤ 20
dictionary[i] consists of lowercase English letters
1 ≤ operations.length ≤ 5 × 10³
1 ≤ word.length ≤ 20
word consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary words and query operations

Process

Generate abbreviations and check for conflicts

Output

Boolean array indicating uniqueness

Key Takeaway

🎯 Key Insight: Use hash map to group dictionary words by abbreviation for O(1) uniqueness checks

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to preprocess dictionary words by grouping them by their abbreviations using a hash map. For each query, check if the abbreviation exists and whether all words with that abbreviation match the query word. Best approach uses hash map preprocessing for O(1) queries. Time: O(1) per query, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Preprocess Abbreviations	O(1)	O(n)	Build hash map of abbreviations to word sets during initialization for O(1) queries
Brute Force - Check All Words Each Time	O(n)	O(1)	For each query, iterate through entire dictionary to check abbreviation conflicts

Hash Map - Preprocess Abbreviations — Algorithm Steps

Step 1: Build hash map from abbreviation to set of original words
Step 2: For query, generate abbreviation and check map
Step 3: Return true if abbreviation not in map or all words match query

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Group dictionary words by abbreviation

Query

Look up abbreviation in O(1) time

Check

Verify uniqueness condition

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_WORDS 100
#define MAX_ABBR 50

typedef struct {
    char words[MAX_WORDS][50];
    int count;
} WordSet;

typedef struct {
    char abbr[20];
    WordSet wordSet;
} AbbrEntry;

typedef struct {
    AbbrEntry entries[MAX_ABBR];
    int size;
} ValidWordAbbr;

void getAbbr(const char* word, char* abbr) {
    int len = strlen(word);
    if (len <= 2) {
        strcpy(abbr, word);
        return;
    }
    sprintf(abbr, "%c%d%c", word[0], len - 2, word[len - 1]);
}

ValidWordAbbr* createValidWordAbbr(char dictionary[][50], int dictSize) {
    ValidWordAbbr* obj = malloc(sizeof(ValidWordAbbr));
    obj->size = 0;
    
    for (int i = 0; i < dictSize; i++) {
        char abbr[20];
        getAbbr(dictionary[i], abbr);
        
        int found = -1;
        for (int j = 0; j < obj->size; j++) {
            if (strcmp(obj->entries[j].abbr, abbr) == 0) {
                found = j;
                break;
            }
        }
        
        if (found == -1) {
            strcpy(obj->entries[obj->size].abbr, abbr);
            obj->entries[obj->size].wordSet.count = 0;
            found = obj->size;
            obj->size++;
        }
        
        bool wordExists = false;
        for (int k = 0; k < obj->entries[found].wordSet.count; k++) {
            if (strcmp(obj->entries[found].wordSet.words[k], dictionary[i]) == 0) {
                wordExists = true;
                break;
            }
        }
        
        if (!wordExists) {
            strcpy(obj->entries[found].wordSet.words[obj->entries[found].wordSet.count], dictionary[i]);
            obj->entries[found].wordSet.count++;
        }
    }
    
    return obj;
}

bool isUnique(ValidWordAbbr* obj, const char* word) {
    char abbr[20];
    getAbbr(word, abbr);
    
    for (int i = 0; i < obj->size; i++) {
        if (strcmp(obj->entries[i].abbr, abbr) == 0) {
            WordSet* wordSet = &obj->entries[i].wordSet;
            if (wordSet->count == 1 && strcmp(wordSet->words[0], word) == 0) {
                return true;
            }
            return false;
        }
    }
    return true;
}

int main() {
    char dictionary[4][50] = {"deer", "door", "cake", "card"};
    ValidWordAbbr* obj = createValidWordAbbr(dictionary, 4);
    
    bool result1 = isUnique(obj, "dear");
    bool result2 = isUnique(obj, "cart");
    bool result3 = isUnique(obj, "cane");
    bool result4 = isUnique(obj, "make");
    
    printf("[%s,%s,%s,%s]\n", 
           result1 ? "true" : "false",
           result2 ? "true" : "false",
           result3 ? "true" : "false",
           result4 ? "true" : "false");
    
    free(obj);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Hash map lookup and set operations are O(1) average case

✓ Linear Growth

Space Complexity

O(n)

Hash map stores abbreviations and word sets for n dictionary words

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Preprocess Abbreviations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler