-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathgenerate_abbreviations.py
More file actions
53 lines (41 loc) · 1.33 KB
/
Copy pathgenerate_abbreviations.py
File metadata and controls
53 lines (41 loc) · 1.33 KB
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
43
44
45
46
47
48
49
50
51
52
53
"""
Generalized Abbreviations
Given a word, return all possible generalized abbreviations. Each
abbreviation replaces contiguous substrings with their lengths.
Reference: https://leetcode.com/problems/generalized-abbreviation/
Complexity:
Time: O(2^n) where n is the length of the word
Space: O(n) recursion depth
"""
from __future__ import annotations
def generate_abbreviations(word: str) -> list[str]:
"""Generate all possible abbreviations of a word.
Args:
word: The input word to abbreviate.
Returns:
A list of all valid abbreviations.
Examples:
>>> sorted(generate_abbreviations("ab"))
['1b', '2', 'a1', 'ab']
"""
result: list[str] = []
_backtrack(result, word, 0, 0, "")
return result
def _backtrack(
result: list[str],
word: str,
position: int,
count: int,
current: str,
) -> None:
"""Recursively build abbreviations by including or skipping characters."""
if position == len(word):
if count > 0:
current += str(count)
result.append(current)
return
if count > 0:
_backtrack(result, word, position + 1, 0, current + str(count) + word[position])
else:
_backtrack(result, word, position + 1, 0, current + word[position])
_backtrack(result, word, position + 1, count + 1, current)