Python solution with detailed explanation


  • 0
    G

    Solution

    Generalized Abbreviation https://leetcode.com/problems/generalized-abbreviation/

    Method1: Backtracking

    class Solution(object):
        def helper(self, word, so_far, i, so_far_len, N):
            if so_far_len == N:
                self.result.append("".join(so_far))
                return
            
            candidates = [word[i]]
            if len(so_far) == 0 or so_far[-1].isdigit() == False:
                for x in range(1, N+1):
                    if so_far_len + x <= N:
                        candidates.append(x)
                        
            for c in candidates:
                c_str = str(c)
                so_far.append(c_str)
                if c_str.isalpha() == False:
                    self.helper(word, so_far, i+c, so_far_len+c, N)
                else:
                    self.helper(word, so_far, i+1, so_far_len+1, N)
                so_far.pop()
            return
        
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            self.result = []
            self.helper(word, [], 0, 0, len(word))
            self.result.reverse()
            return self.result
    

    Method2: Subset Based Solution

    • How many valid abbreviations can there be? Each word may be included or not included and replaced by 1. Therefore we have 2^N possible abbreviations.
    • The code for this method is straight-forward after this amazing insight! Either select the word and add to so_far, otherwise do not select and add 1.
    • At process solution step, process the solution to compress all the 1s.
    class Solution(object):
        def compress(self, so_far):
            csofar, i = [], 0
            while i < len(so_far):
                if so_far[i].isalpha():
                    csofar.append(so_far[i])
                    i += 1
                else:
                    num = 0
                    while i < len(so_far) and so_far[i].isdigit():
                        num += 1
                        i += 1
                    csofar.append(str(num))
            return "".join(csofar)
        
        def helper(self, i, word, so_far, result):
            if i == len(word):
                result.append(self.compress(so_far))
            else:
                so_far.append(word[i])
                self.helper(i+1, word, so_far, result)
                so_far.pop()
                so_far.append("1")
                self.helper(i+1, word, so_far, result)
                so_far.pop()
                return
        
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            result = []
            self.helper(0, word, [], result)
            return result
    

Log in to reply
 

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