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

发布时间：2020-12-20 09:54:21 所属栏目：Python 来源：网络整理

导读：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”,“1o

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”]?

思路：递归+回溯

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

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


     helper(self,index,temp_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,temp_res+'1',count+1)

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

只能看代码慢慢理解了。

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!