C++, my not very fast but easy to understand solution


  • 0
    B

    My thought is enumerating number of left characters that is going to be left in the abbreviation
    Starting from 1 to n
    If for example the word is of length N, and we need to pick M characters left. Then I will enumerate all combinations of N pick M. ...

    class Solution {
        /// Although I don't really sure what back-tracking is
        /// I guess this is also a kind of back tracking
        void makeWord(const string& word, int prev_start, int start, int ch_num, list<string> &composing, vector<string> & result)
        {
            if (start == word.size() || ch_num == 0) {
                int tail_d = -1;
                if (ch_num == 0 && start < word.size()) {
                    tail_d = word.size() - start;
                    composing.push_back(to_string(tail_d));
                }
                string composed;
                for (auto& s:composing) {
                    composed.append(s);
                }
                result.push_back(composed);
                if (tail_d != -1) {
                    composing.pop_back();
                }
                return;
            }
            for (int i = start; i <= word.size()-ch_num; ++i) {
                int d = i-start;
                string prefix = "";
                if (d > 0) {
                    prefix = to_string(d);
                }
                composing.push_back(prefix);
                composing.push_back(string(1, word[i]));
                makeWord(word, i, i+1, ch_num-1, composing, result);
                composing.pop_back();
                composing.pop_back();
            }
        }
    public:
        vector<string> generateAbbreviations(string word) {
            /// Corner case
            if (word.size() == 0) return vector<string>(1, "");
            /// Always have a case where a number represents the whole word
            vector<string> result(1, to_string(word.size()));
            int N = word.size();
            /// Starting from only 1 char left in the abbr, and all others are number, 
            /// so it becomes a N pick ch_num problem, just have to enumerate all the combinations of 
            /// the N pick ch_num
            for (int ch_num = 1; ch_num <= N; ch_num++) {
                // (Pick ch_num of chars out from N chars)
                list<string> aword;
                makeWord(word, -1, 0, ch_num, aword, result);
            }
            return result;
        }
    };
    

Log in to reply
 

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