Simple python solution w/ explanation


  • 0
    P

    The idea is probably similar to some of the other answers here. For any particular letter in a word, it can either be abbreviated or used as it is. We then recursively do the same for the rest of the string.

    In particular about the actual abbreviation, an alphabet can be either abbreviated to a:

    • '1' if the previous letter (word[i-1]) was not abbreviated or,

    • 1 + abbreviation(word[i-1]). For e.g. w2d was made using the following recursive sequence:

        `w` + f(ord)
        `w` + '1' + f(rd)
        `w` + '1' + '1' + f(d)
        `w` + '2' + f(d)
        `w` + '2' + 'd'
      

    Here's the python code:

    class Solution(object):
        def generateAbbreviations(self, word):
            """
            :type word: str
            :rtype: List[str]
            """
            if not word:
                return [""]
    
            def helper(current, rem, answers):
                if len(rem) == 0:
                    answers.append(current)
                    return
    
                # print "current = %s, rem = '%s', answers = %s" % (current, rem, answers)
                if len(current) > 0 and current[-1].isdigit():
                    helper(current[:-1] + str(int(current[-1])+1), rem[1:], answers)
                else:
                    helper(current+str(1), rem[1:], answers)
                helper(current+rem[0], rem[1:], answers)
    
            answers = []
            helper("", word, answers)
            return answers

  • 0
    J

    Would this work if the word has more than 19 characters?

    str(int(current[-1])+1) would return 10 if current[-1] == 9. But suppose current[-1] is 9 and current[-2] is 1. It looks like this would return 110 instead of 20.


Log in to reply
 

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