# 10 line DP C++ solution

• We can use DP to solve this problem:
Rule 1. either we make all remaining characters to the right part of abbreviation
Rule 2. make current character position not abbreviation and prefix it to all possible abbreviations of string starting from next character
Rule 3. abbreviate a substring starting from current character, add 'next character' as is, and make it as prefix to all possible abbreviations for substring after the next character

Example:
Given abbreviations of ‘’ is [""]
and that of ‘b' is: ["1","b"]
and that of ‘ab' is: ["2","1b","a1","ab”]

We can compute abbreviations of “cab” as:
From Rule 1. "3"
From Rule 2. "c2","c1b","ca1","cab"
From Rule 3.
(choose ‘a’ as next character) "1a1",”1ab”
(choose ‘b’ as next character) "2b"

``````vector<string> generateAbbreviations(string word) {
vector<vector<string>> dp(word.size()+1, vector<string>());
dp[word.size()].push_back("");

for(int i=word.size()-1;i>=0;i--){
dp[i].push_back(to_string(word.size()-i));

for(int j=i+1;j<word.size();j++)
for(string s : dp[j+1])
dp[i].push_back(to_string(j-i)+word[j]+s);

for(string t : dp[i+1])
dp[i].push_back(word[i]+t);
}

return dp[0];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.