320. (locked)Generalized Abbreviation

Difficulty: Medium

Frequency: N/A

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"]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
        vector<string> generateAbbreviations(string word) {
                vector<string> results;
                string tmp;
                helper(word, 0, tmp, results);
                return results;
        }
        void helper(string word, int idx, string tmp, vector<string> &results) {
                if (idx == word.size()) {
                        results.push_back(tmp);
                        return;
                }
                helper(word, idx + 1, tmp + word[idx], results);
                for (int i = 1; i < word.size() - idx; i++)
                        helper(word, idx + 1 + i, tmp + to_string(i) + word[idx + 1], results);
                helper(word, word.size(), tmp + to_string(word.size() - idx), results);
        }
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s