320. Generalized Abbreviation
A word's generalized abbreviation can be constructed by taking any number of non-overlapping and non-adjacent 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")
"5" ("abcde" turned into "5")
"abcde" (no substrings replaced)
However, these abbreviations are invalid:
"23" ("ab" turned into "2" and "cde" turned into "3") is invalid as the substrings chosen are adjacent.
"22de" ("ab" turned into "2" and "bc" turned into "2") is invalid as the substring chosen overlap.
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 ≤ 15
word consists of only lowercase English letters.
Approach #1 (Backtracking)
How many abbreviations are there for a word of length n ? The answer is 2^n
because each character can either be abbreviated or not, resulting in different abbreviations.
Algorithm :-
The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in several choices to give all the possible solutions to the problem.
The completion is done incrementally, by extending the candidate in many steps.
Abstractly, the partial candidates can be seen as nodes of a tree, the potential search tree.
Each partial candidate is the parent of the candidates that derives from it by an extension step;
the leaves of the tree are the partial candidates that cannot be extended any further.
In our problem, the partial candidates are incomplete abbreviations that can be extended by one of the two choices:
keep the next character;
abbreviate the next character.
We extend the potential candidate in a depth-first manner.
We backtrack when we reach a leaf node in the search tree.
All the leaves in the search tree are valid abbreviations and shall be put into a shared list which will be returned at the end.
public class Solution {
public List generateAbbreviations(String word){
List ans = new ArrayList();
backtrack(ans, new StringBuilder(), word, 0, 0);
return ans;
}
// i is the current position
// k is the count of consecutive abbreviated characters
private void backtrack(List ans, StringBuilder builder, String word, int i, int k){
int len = builder.length(); // keep the length of builder
if(i == word.length()){
if (k != 0) builder.append(k); // append the last k if non zero
ans.add(builder.toString());
} else {
// the branch that word.charAt(i) is abbreviated
backtrack(ans, builder, word, i + 1, k + 1);
// the branch that word.charAt(i) is kept
if (k != 0) builder.append(k);
builder.append(word.charAt(i));
backtrack(ans, builder, word, i + 1, 0);
}
builder.setLength(len); // reset builder to the original state
}
}
Complexity Analysis:
Time complexity : 2* O(n^2n).
For each call to backtrack, it either returns without branching, or it branches into two recursive calls.
All these recursive calls form a complete binary recursion tree with 2^n leaves and 2−12^n−1 inner nodes.
For each leaf node, it needs O(n) time for converting builder to String;
for each internal node, it needs only constant time.
Thus, the total time complexity is dominated by the leaves.
In total that is 2* O(n^2n).
Space complexity: O(n)
If the return list doesn't count, we only need )O(n) auxiliary space to store the characters in StringBuilder and the O(n) space used by system stack.
In a recursive program, the space of system stack is linear to the maximum recursion depth which is n in our problem.
