320. Generalized Abbreviation
Write a function to generate the generalized abbreviations of a word.
Note: The order of the output does not matter.
Example:
Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
// Backtracking
vector<string> generateAbbreviations(string word) { // time: O(2^n); space: O(2^n)
vector<string> res;
string cur;
helper(word, res, cur, 0, 0);
return res;
}
void helper(string& word, vector<string>& res, string cur, int idx, int count) {
if (idx >= word.size()) {
if (count) cur += to_string(count);
res.push_back(cur);
} else {
helper(word, res, cur, idx + 1, count + 1); // abbreviate the current char
if (count) cur += to_string(count);
helper(word, res, cur + word[idx], idx + 1, 0); // use the current char after adding the count number to cur
}
}
// Bit Manipulation
vector<string> generateAbbreviations(string word) { // time: O(2^n); space: (2^n)
vector<string> res;
int n = word.size();
for (int i = 0; i < pow(2, n); ++i) {
string cur;
int count = 0;
for (int j = 0; j < n; ++j) {
if ((i >> j) & 1) { // abbreviate
++count;
} else { // use the current char
if (count) {
cur += to_string(count);
count = 0;
}
cur += word[j];
}
}
if (count) cur += to_string(count);
res.push_back(cur);
}
return res;
}
Last updated
Was this helpful?