My 99% DP solution in C++


  • 0
    D
    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].


Log in to reply
 

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