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.
Example 1:
Input: word = "word" Output: ["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"]
Example 2:
Input: word = "a" Output: ["1","a"]
Constraints:
1 <= word.length <= 15word consists of only lowercase English letters.
The description was taken from https://leetcode.com/problems/generalized-abbreviation/solution/.
#O(N*2^N) Time, O(N*2^N) Space
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
output = []
def backtrack(start:int, combo:list) -> None:
if start == len(word):
output.append("".join(combo))
return
combo.append(word[start])
backtrack(start+1, combo)
combo.pop()
for i in range(1, len(word)-start+1):
if not combo or not combo[-1].isnumeric():
combo.append(str(i))
backtrack(start+i, combo)
combo.pop() backtrack(0,[])
return outputThe problem description is a bit confusing but it is basically saying that we can replace substrings with their lengths but the number abbreviations can't be right next to each other.
For example:
Input: 'word'
Combinations would include:
4: (length of 'word')
3d: (length of 'wor') + ('d')
1o2: (length of 'w') + ('o') + (length of 'rd')
If a problem requires us to return all possible combinations of a given input, typically that is an indication that backtracking is a good approach.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, if not, check if a placement is valid then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
Let's start by creating our output array that we will append each valid combination to.
output = []
Next, we will create our dfs function.
The function will take a starting index to set the left bounds of each substring or abbreviation from and a current DFS path's combination.
def backtrack(start:int, combo:list) -> None:
The base case for our recursive function that we will need to check is if that starting index has reached the ending index.
If that is the case, then we have nothing more to add to the current DFS path's combination and we can append the string to the output and return from the function.
if start == len(word):
output.append("".join(combo))
return
With this problem, we basically have two choices.
We can either keep the current portion of the string and slap the next letter on, or we can abbreviate the next letter and slap a number on instead.
Let's first choose the easy option to keep the current portion of the string. We don't have to check if this placement is valid because whether we can place a character doesn't depend on what is in the current combination, we can just place it.
Once we have placed the character at the starting index we were given by the function call, we will continue down the DFS path of this combination.
combo.append(word[start])
backtrack(start+1, combo)
Once the DFS yoyo has returned back to here, we will backtrack on our decision to place the current character by popping it off of our combination.
This will allow us to circulate a different value into this spot, namely a number in just a moment.
combo.pop()
Now, we will see if we can make a valid placement of a number abbreviation. This choice is a bit more complicated.
We will need to create a loop that will generate numbers for us to slap on the end of the current combo. This number will be the remaining substring length of the current word.
for i in range(1, end-start+1):
In order to make this placement, we will either need an empty combination or the current combination can't have a number as its last character. We don't want combinations like "121" for "word".
if not combo or not combo[-1].isnumeric():
If either one of these conditions is true, then we will circulate a number abbreviation to the current combination and exhaust this combination's DFS path, similar to the character placement we just made.
combo.append(str(i))
backtrack(start+i, combo)
Once the DFS yoyo returns, we will pop off the number we just placed to make room for a character later.
combo.pop()
Now that we have our backtrack function built, we just need to make the initial call by passing a starting index of zero and an empty combo list.
When the output has been filled with all generalized abbreviations, we will return it.
backtrack(0,[])
return output
The time and space complexity are extremely tricky for this one, but an intuitive estimation would be n*2^n. 2^n is the traditional space complexity for a backtracking algorithm since each index may require two choice child branches within a recursive tree and the join() function requires a time complexity of n.