Python solution with detailed explanation

  • 1


    Minimum Unique Word Abbreviation


    • This problem is a combination of the other two related problems.
    • Use the approach of “320. Generalized Abbreviation” to generate all abbreviations of “target”.
    • Notice how we modify process_solution so that we also return the count correctly as specified in the problem.
    • With each abbreviation, check whether it’s an abbreviation of any word in the dictionary using the approach of “408. Valid Word Abbreviation”
    • Preprocess the dictionary to remove those words which can never have same abbreviation as target. Refer to this for explanation:
    class Solution(object):
        def extract_number(self, j, abbr, M):
            num = 0
            while j < M and abbr[j].isdigit():
                num, j = num*10 + int(abbr[j]), j+1
            return num, j
        def valid(self, word, abbr):
            i,j,N, M = 0,0,len(word), len(abbr)
            while i < N and j < M:
                if abbr[j].isalpha() and abbr[j] != word[i]:
                    return False
                elif abbr[j].isalpha() and abbr[j] == word[i]:
                    i,j = i+1,j+1
                elif abbr[j].isdigit():
                    if abbr[j] == '0':
                        return False
                    num, j = self.extract_number(j, abbr, M)
                    i = i+num
            return (i==N and j == M)
        def process_solution(self, so_far):
            csofar, i, cnt = [], 0, 0
            while i < len(so_far):
                if so_far[i].isalpha():
                    i, cnt = i+1, cnt+1
                    num = 0
                    while i < len(so_far) and so_far[i].isdigit():
                        num, i = num+1, i+1
                    cnt = cnt + 1
            return "".join(csofar), cnt
        def test(self, abbr, dictionary):
            for wrd in dictionary:
                if self.valid(wrd, abbr):
                    return False
            return True
        def helper(self, word, so_far, i, dictionary):
            if i == len(word):
                abbr, cnt = self.process_solution(so_far)
                if cnt < self.result_len and self.test(abbr, dictionary):
                    self.result, self.result_len = abbr, cnt
                self.helper(word, so_far, i+1, dictionary)
                self.helper(word, so_far, i+1, dictionary)
        def minAbbreviation(self, target, dictionary):
            :type target: str
            :type dictionary: List[str]
            :rtype: str
            # Remove those words which can never be an abbreviation for target.
            # This preprocessing will help us save time.
            filtered_dictionary = []
            for wrd in dictionary:
                if len(wrd) != len(target):
            dictionary = filtered_dictionary
            if len(dictionary) == 0:
                return str(len(target))
            self.result_len = len(target)+1
            self.result, so_far, i = target, [], 0
            self.helper(target, so_far, i, dictionary)        
            return self.result

Log in to reply

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