Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
class Solution { public: vector<string> generateAbbreviations(string word) { vector<string>res; dfs(0,"",res,false,word); return res; } private: void dfs(int idx,string tmp,vector<string>&res,bool prevNum,string word) { if(idx==word.size()){ res.push_back(tmp); return; } dfs(idx+1,tmp+word[idx],res,false,word); if(!prevNum) { for(int len = 1;len+idx<=word.size();len++) { dfs(idx+len,tmp+to_string(len),res,true,word); } } } };
原文：http://www.cnblogs.com/jxr041100/p/7899114.html