LeetCode Q320: Generalized Abbreviation

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

Solution:
I was totally confused when this question first come to me. I can't figure out what pattern is hidden behind example results.

However, if you can consider a string a bit array, then represent it using digit or characters is no difference than setting bit to 1 or 0.

So, for a given string with n characters, there are totally 2^n ways to represent it

When this is clear, we can easily solve it using backtracking. Although we could even use bit manipulation to speed up, due to time limitation, we use a vector instead.

	class Solution {
	public:
	void helper(string word, vector<string>& res, vector<int>& mark, int depth){
	if(depth==word.length()-1){
	string s;
	int c=0;
	for(int i=0; i<mark.size(); i++){
	if(mark[i]==1){
	c++;
	}else{
	s=c==0?s+string(1, word[i]):s+to_string(c)+string(1, word[i]);
	c=0;
	}
	}
	if(c!=0)
	s=s+to_string(c);
	res.push_back(s);
	return;
	}
	helper(word, res, mark, depth+1);
	mark[depth+1]=1;
	helper(word, res, mark, depth+1);
	mark[depth+1]=0;
	}
	vector<string> generateAbbreviations(string word) {
	vector<string> res;
	if(word.length()==0){
	res.push_back(string(""));
	return res;
	}
	vector<int> mark(word.length(), 0);
	helper(word, res, mark, 0);
	mark[0]=1;
	helper(word, res, mark, 0);
	return res;
	}
	};

view raw Q320.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	vector<string> generateAbbreviations(string word) {
	vector<string> res;
	if(word.length()==0){
	string tmp("");
	res.push_back(tmp);
	return res;
	}
	int num = pow(2, word.length());
	for(int i=0; i<num; i++){
	string cur;
	int ones=0;
	int p = 0;
	int j=i;
	for(int q=0; q<word.length(); q++){
	if(j&1!=0)
	ones++;
	else{
	if(ones!=0)
	cur = cur + to_string(ones);
	cur = cur + string(1, word[p]);
	ones=0;
	}
	p++;
	j=j>>1;
	}
	if(ones!=0)
	cur = cur + to_string(ones);
	res.push_back(cur);
	}
	return res;
	}
	};

view raw Q320Rnd2.cpp hosted with ❤ by GitHub