【python-子集】Generalized Abbreviation（广义缩写）

Write a function to generate the generalized abbreviations of a word.

Example: Given word = “word”, return the following list (order does not matter): [“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]

思路：递归 回溯

代码语言：javascript复制

class Solution(object):
    def generateAbbreviations(self, word):
        """ :type word: str :rtype: List[str] """

        res = []
        #从0开始遍历，最后0用于计数
        self.helper( 0, word, "", res, 0)
        return res


    def helper(self, index, word, temp_res, res, count):
        #注意这里是len(word)，不是len(word)-1
        if index==len(word):
            if count!=0:
                #组合新的字符串
                temp_res = temp_res[0:-count]   str(count)
            res.append( temp_res )
            return

        # append 1
        self.helper( index 1, word, temp_res '1', res, count 1)

        # append word
        if count!=0:
            temp_res = temp_res[0:-count]   str(count)
        self.helper( index 1, word, temp_res word[index], res, 0)  
s=Solution()
print(s.generateAbbreviations("word"))

只能看代码慢慢理解了。

参考：https://www.it610.com/article/5456538.htm

function list return word 递归

0 人点赞