i18n

Interview

Time limit1sMemory limit128 MB

Summary
Given text lines, expand i18n-style abbreviations back into previously seen full words when the expansion is valid and unique, preserving capitalization and separators.
Level

Medium5 of 10

Topics
String, Hash map, Implementation
Solved
No attempts yet

Problem

Internationalization and localization are long words that are commonly abbreviated as i18n and l10n. The number between the first and last letters is the count of letters that were omitted. This is a powerful abbreviation scheme that can be applied naturally to any word.

A word may be abbreviated only if it has already appeared earlier in the text. To abbreviate a word, keep only its first and last letters and replace every letter in between with the count of omitted letters.

Your task is to write a program that expands such abbreviations in a given text wherever possible. An abbreviation can be expanded only if the expansion is both valid and unambiguous.

  • An expansion is valid if the full word has appeared earlier in the text and its abbreviated form matches the abbreviation being expanded. Case is ignored when checking validity. For example, expanding i18n to internationalization is valid (even if internationalization previously appeared only with a capital I). Expanding p14n to parameterization is not valid, because parameterization never appeared before the abbreviation. Expanding a11n to abbreviation is not valid, because a11n is not the correct abbreviation of abbreviation (the correct one is a10n).
  • An expansion is unambiguous if exactly one valid expansion exists. For example, l10n unambiguously expands to localization, but p5m cannot be expanded unambiguously, because both problem and program abbreviate to p5m.

Input

The input contains at most 1000 lines, each with at most 80 characters. Each line contains one or more words separated by spaces and the special symbols -, ,, ., ", (, ), :, ;, !, ?. There are no trailing spaces, but a line may end with one of the other separators.

Each word is either full or abbreviated.

  • A full word consists of 1 to 32 Latin letters and appears in one of three capitalization forms: all lowercase, First capital letter, or ALL CAPITAL LETTERS.
  • An abbreviated word consists of a Latin letter, followed by a number from 2 to 30 (without a leading zero), followed by a Latin letter. Abbreviated words use the three corresponding capitalization forms: all l7e, F3t C5l L4r, or ALL C5L L5S.

Output

Reproduce the original text with its original separators, expanding abbreviated words into full words wherever possible (as described above). The capitalization of an expanded word must match the capitalization of the abbreviation it replaces.

Leave invalid or ambiguous abbreviations unchanged (still abbreviated). Note that lines in the output may be longer than 80 characters.

Examples6

  1. Example 1

    Input
    The first line of sample input.
The s4d l2e of s4e i3t.
Lone, lone, l4e...
S4e input last l4e!
    Expected output
    The first line of sample input.
The s4d line of sample input.
Lone, lone, l4e...
Sample input last l4e!

  2. Example 2

    Input
    problem program p5m
    Expected output
    problem program p5m

  3. Example 3

    Input
    localization rocks l10n
    Expected output
    localization rocks localization

  4. Example 4

    Input
    internationalization matters. I18N
    Expected output
    internationalization matters. INTERNATIONALIZATION

  5. Example 5

    Input
    Abbreviation a10n a11n
    Expected output
    Abbreviation abbreviation a11n

  6. Example 6

    Input
    The p14n is unknown.
    Expected output
    The p14n is unknown.