leetcode-solution/Python/0320-generalized-abbreviation.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# time complexity: O(2^n)
# space complexity: O(n)
from typing import List


class Solution:
    def storeAbbreviations(
        self,
        abbreviations: List[str],
        word: str,
        currWord: str,
        index: int,
        abbreviatedCount: int
    ):
        if index == len(word):
            if abbreviatedCount > 0:
                currWord += str(abbreviatedCount)
            abbreviations.append(currWord)
            return

        self.storeAbbreviations(
            abbreviations,
            word,
            currWord
            + (str(abbreviatedCount) if abbreviatedCount > 0 else "")
            + word[index],
            index + 1,
            0
        )

        self.storeAbbreviations(
            abbreviations, word, currWord, index + 1, abbreviatedCount + 1
        )

    def generateAbbreviations(self, word: str) -> List[str]:
        abbreviations = []
        self.storeAbbreviations(abbreviations, word, "", 0, 0)
        return abbreviations


word = "word"
print(Solution().generateAbbreviations(word))