L 320. Generalized Abbreviation ---M

 Write a function to generate the generalized abbreviations of a word. 

Note: The order of the output does not matter.

Example:

Input: "word"
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

 

A:

就是每加入点， 选择把他变成之前的所有

依然是all permuation 类似的问题。  一个个加入就可以了

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> res;
        int n = word.length();        
        vector<vector<string>> V{vector<string>{""}};
        for(int i =0;i<word.length(); i++){
            char ch = word[i];
            vector<string> curM;
            for(int start = 0; start <= i; start++){// merged [start, i]
                for(auto& t : V[start]){
                    if(start == i){
                        curM.push_back(t+string(1,ch));
                    }
                    // cannot have two consecutive number as abbreviation
                    if(t.length()==0 ||  not isdigit(t.back()) ){
                        curM.push_back(t + to_string(i- start + 1));
                    }
                }
            }
            V.push_back(curM);
        }
        return V.back();
    }
};