```
class Solution {
public:
vector<string> generateAbbreviations(string word) {
int N = word.size();
vector<vector<string>> dp(N + 2);
dp[N].emplace_back();
dp[N + 1].emplace_back();
for (int i = N - 1; i >= 0; --i) {
for (auto& s : dp[i + 1]) {
dp[i].push_back(word[i] + s);
}
for (int j = 1; i + j <= N; ++j) {
string sub = word.substr(i, min(j + 1, (int)word.size() - i));
sub.replace(0, j, to_string(j));
for (auto& s : dp[i + j + 1]) {
dp[i].push_back(sub + s);
}
}
}
return dp[0];
}
};
```

The idea is using dp to reduce redundant calculation. The subproblem is defined as abbreviations of word.substr(i). And for each subproblem, we have two choices, one is to keep word[i], the other is to replace first j characters with number and concatenate word.substr(i, j + 1) with results in dp[i + j + 1].