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