Unique Abbreviations II


  • 2
    F

    In my interview, as a follow up, i was asked the following question:

    An abbreviation can be anything now (alpha-numeric). each number is considered length = 1 and each character is considered length = 1.

    Examples:
    "internationalization" -> 20, i19, 19n, i18n
    "localization" -> 12, l11, 11n, l10n
    “dog” -> 3, d2, 2d, d1g
    “accessibility” -> 13, a12, 12y, a11y, ac11 
    “automatically” -> 13, a12, 12y, a11y,  au11
    
    Abbreviation lengths:
    internationalization -> 20 -> len = 1
    localization -> l11 -> len = 2
    automatically -> a11y -> len = 3
    

    Question:
    For a given dictionary of words, find all the unique abbreviations with the least length.

    List<String> findUniqueAbbreviations( List<String> dict )
    

    Example:
    Dictionary: internationalization, localization, dog, accessibility, automatically

    Result: word -> abbreviations
    "internationalization" -> 20
    "localization" -> 12
    "dog" -> 3
    "accessibility" -> ac11 
    "automatically" -> au11
    
     selecting abbreviations like "13", "a12", "12y", "a11y" for either 
     accessibility or automatically will break the "unique" rule

  • 0
    F
    class Abbreviation:
    
        def __init__(self, string):
    
            self.string = string
    
    
        def __iter__(self):
    
            yield len(self.string)
    
            for i in range(1, len(self.string)):
    
                yield self.string[:i] + str(len(self.string[i:]))
    
                yield str(len(self.string)-i) + self.string[-i:]
    
    
    words = [
        "internationalization",
        "localization",
        "dog",
        "accessibility",
        "automatically",
        "autocorrection"
    ]
    
    abbrs = {
        w: Abbreviation(w).__iter__()
        for w in words
    }
    
    final_abbrs = {}
    
    collisions = []
    
    
    while True:
    
        for c in set(collisions):
    
            words += final_abbrs[c]
            del final_abbrs[c]
    
        collisions = []
    
        for w in words:
    
            a = abbrs[w]
            abbr = next(a)
    
            if abbr in final_abbrs:
    
                collisions.append(abbr)
                final_abbrs[abbr].append(w)
    
            else:
    
                final_abbrs[abbr] = [w]
    
        words = []
    
    
        if not collisions:
            break
    
    
    return list(final_abbrs.keys())

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.