Leetcode 320 Generalized Abbreviation
A word’s generalized abbreviation can be constructed by taking any number of non-overlapping substrings and replacing them with their respective lengths. For example, “abcde” can be abbreviated into “a3e” (“bcd” turned into “3”), “1bcd1” (“a” and “e” both turned into “1”), and “23” (“ab” turned into “2” and “cde” turned into “3”).
Given a string word, return a list of all the possible generalized abbreviations of word. Return the answer in any order.
Input: word = "word"
Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
Input: word = "a"
Output: ["1","a"]
- Eklenecek
def generateAbbreviations(self, word):
"""
:type word: str
:rtype: List[str]
"""
def generateAbbreviationsHelper(word, i, cur, res):
if i == len(word):
res.append("".join(cur))
return
cur.append(word[i])
generateAbbreviationsHelper(word, i + 1, cur, res)
cur.pop()
if not cur or not cur[-1][-1].isdigit():
for l in xrange(1, len(word) - i + 1):
cur.append(str(l))
generateAbbreviationsHelper(word, i + l, cur, res)
cur.pop()
res, cur = [], []
generateAbbreviationsHelper(word, 0, cur, res)
return res