10 line DP C++ solution


  • 0
    A

    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];
        }
    

Log in to reply
 

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