# Python solution with detailed explanation

• Solution

Minimum Unique Word Abbreviation https://leetcode.com/problems/minimum-unique-word-abbreviation/

Algorithm

• 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:https://discuss.leetcode.com/topic/61349/insights-optimizing-hacking
``````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():
csofar.append(so_far[i])
i, cnt = i+1, cnt+1
else:
num = 0
while i < len(so_far) and so_far[i].isdigit():
num, i = num+1, i+1
cnt = cnt + 1
csofar.append(str(num))
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
return
else:
so_far.append("1")
self.helper(word, so_far, i+1, dictionary)
so_far.pop()
so_far.append(word[i])
self.helper(word, so_far, i+1, dictionary)
so_far.pop()

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):
continue
filtered_dictionary.append(wrd)
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
``````

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