Fork me on GitHub

Generalized Abbreviation

Posted on

Description

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

Note: The order of the output does not matter.

Example:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> ret;
        string current = "";
        helper(word, word.size(), 0, current, ret);
    }
    
    void helper(string word, int size, int index, string current, vector<string> ret) {
        if(index == size) {
            ret.push_back(current);
            return;
        }
        
        
        for(int i = index; i < size; ++i) {
            helper(word, size, i + 1, 
               current + word.substr(index, i - index + 1), ret);
        }
        return;
    }
};