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"]
// 52ms, 85%
class Solution {
private:
void gen(const string& word, string prefix, vector<string>& res) {
res.emplace_back(prefix + word);
for (int len = 1; len <= word.size(); len++) {
for (int i = 0; i <= word.size() - len; i++) {
string s = prefix;
if (i > 0) s += word.substr(0, i);
s += to_string(len);
if (i + len < word.size())
s += word[i+len];
if (i + len + 1 >= word.size())
res.emplace_back(s);
else {
gen(word.substr(i + len + 1), s, res);
}
}
}
}
public:
vector<string> generateAbbreviations(string word) {
vector<string> res;
gen(word, "", res);
return res;
}
};