# Generalized abbreviation

• Given an Generalized abbreviation function:
for example for the word "word"
f(word) would return: word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4

• ``````class Solution {
private:
bool isDigit(char c){
return (c>='0' && c<='9');
}

string intToString(int a){
string s="";

while(a){
s+=('0' + a%10);
a/=10;
}

return s;
}

void solve(string word,set<string>& ans){
int n=word.size(),i,j,k,num,d;

if(ans.count(word)==0){
ans.insert(word);
}else{
dup++;
return;
}

for(i=0;i<n;i++){
if(!isDigit(word[i])){
string s = "";
int num=1;
for(j=i-1,d=1;j>=0;j--,d*=10){
if(!isDigit(word[j]))
break;
num = num + d*(word[j]-'0');
}

for(k=0;k<=j;k++)
s+=word[k];

int cur=0;
for(j=i+1;j<n;j++){
if(!isDigit(word[j]))
break;
cur = cur*10 + word[j]-'0';
}

s+=intToString(cur+num);

for(k=j;k<n;k++)
s+=word[k];

solve(s,ans);
}
}

}

public:
set<string> f(string word){
set<string> ans;
solve(word,ans);
return ans;
}
};``````

• This is my solution, suppose we don't allow results like "11rd" or "12d" which has two digits adhere together (as I don't see them from the question), anyway, the solution is probably not the best one, but it works. For input string `"word"`, it outputs:
`[wor1, 2rd, 1o1d, 1ord, w2d, 1or1, w1r1, 2r1, 3d, 1o2, 4, w1rd, wo2, wo1d, w3, word]`, for input string "wor", it outputs `[2r, 1o1, 3, 1or, wo1, w1r, wor, w2]`, and for input string `"w"`, it outputs `[1, w]`.

Here is the Java code using recursion:

``````public Set<String> generate(String word) {
int n = word.length();
Set<String> res = new HashSet<>();

for (int i = 0; i < n; i++) {
for (int len = 0; len <= n - i; len++) {
String a = word.substring(0, i);
String b = len > 0 ? String.valueOf(len) : "";
String c = word.substring(i + len);

if (c.length() >= 2) {
Set<String> rest = generate(c.substring(1));

for (String d : rest)
res.add(a + b + c.substring(0, 1) + d);
}
}
}

return res;
}
``````

• Python recursive solution:

``````def abbreviate(s):
# abbreviate outputs all possible abbreviation of a word:
# ex: word-> w1rd, wo1d, wor1, 1ord, 1o1d, wo2
if not s:
return ['']
else:
res = abbreviate(s[:-1])
return [w + s[-1] for w in res] + [extendWordWith1(w) for w in res]

def extendWordWith1(word):
if word and word[-1].isdigit():
#if the end of the word is a number, add 1 to that number
idx = len(word)-1
while idx-1>=0 and word[idx-1].isdigit():
idx -=1
return word[:idx] + str(int(word[idx:]) + 1)
else:
return word+'1'``````

• No need of using set, java version.

``````public List<String> transfer(String string) {
List<String> result = new ArrayList<String>();
int length = string.length();
helper(result, string, 0, length);
return result;
}

public void helper(List<String> list, String string, int index, int length) {
for (int i = index; i < length; i++) {
String left = string.substring(0, i);
String right = string.substring(i + 1);
String t = left + "*" + right;//turn string abc into *bc and all the possibility
helper(list, t, i+1, t.length());
}
}
public String handle(String str){//handle *b* to 1b1.. count the apperance of *
int len = 0;
StringBuilder sb = new StringBuilder();
int start =0;
while(start < str.length()){
if(str.charAt(start)=='*'){
len++;
start++;
}
else{
if(len>0){
sb.append(len);
len=0;
sb.append(str.charAt(start++));
}
else sb.append(str.charAt(start++));
}
}
if(len>0) sb.append(len);
return sb.toString();
}``````

• Here is my solution. I know maybe it's not efficient but here it is. But the final result should be refined too as it outputs the result like this for "word"

``````[wor1, 111d, 11rd, 1o1d, 1ord, 11r1, 1o11, 1or1, w111, w1r1, wo11, 1111, w1rd, w11d, wo1d, word]
``````

Here is the code:

``````public static Set<String> abbreviation (String word){
Map<String, HashSet<String>> res = new HashMap<>();

Abb(word, res);

return res.get(word);
}

public static void Abb(String word, Map<String ,HashSet<String>> res){
if (word.length() == 1){
if (!res.containsKey(String.valueOf(word.charAt(0)))) {
HashSet<String> tmpSet = new HashSet<>();

res.put(String.valueOf(word.charAt(0)), tmpSet);
}
}
else {
Abb(word.substring(1), res);
Abb(word.substring(0, (word.length() - 1)), res);
HashSet<String> concatSet = new HashSet<>();

for(String rightStr: res.get(word.substring(1)))
for(String leftStr: res.get(word.substring(0, word.length() - 1)))
if (leftStr.substring(1, leftStr.length()).equals(rightStr.substring(0, rightStr.length() - 1)))

res.put(word, concatSet);
}
}``````

• public class GeneralizedAbbreviation {

``````public static void main(String[] args) {
String s = "word";
GeneralizedAbbreviation ga = new GeneralizedAbbreviation();
ga.process(s);
}
/**
*
* @param s:  word
* @return  word, 1ord, w1rd, wo1d, wor1, 2rd, w2d, wo2, 1o1d, 1or1, w1r1, 1o2, 2r1, 3d, w3, 4
*/
public void process(String s){
int length = s.length();
double pool = Math.pow(2, length)-1;
for(Integer i=0x0;i<=(byte)pool;i++){
StringBuffer finalString = new StringBuffer();
String s1 = i.toBinaryString(i);
String s2 = s.substring(0,length-s1.length());

finalString.append(s2);

int count=0;
for(int j=0;j<s1.length();j++){
if( s1.charAt(j)=='0' ){
if(count!=0){
finalString.append(count);
count=0;
}
finalString.append(s.charAt(length-s1.length()+j));
}else{//==1
count++;
}
}
if(count!=0){
finalString.append(count);
}
System.out.println(finalString.toString());
}
}
``````

}

• //O(2^n) time complexity solution. At each position we can either add a number of a character.

``````public ArrayList<String> convert(String str) throws NullPointerException
{
if(str==null)
{
throw new NullPointerException();
}
if(str.length()==0)
{
return Collections.<String>emptyList();
}

return abbreviate(0,str);
}

private ArrayList<String> abbreviate(int idx,String s)
{
ArrayList<String> ls;
if(idx==s.length()-1)
{
ls=new ArrayList<String>();
return ls;
}
ls=abbreviate(idx+1,s);
ArrayList<String> newResults=new ArrayList<String>();
for(String s:ls)
{
StringBuilder sb;

sb=new StringBuilder(s.length()+1);
sb.append(s.charAt(idx));
sb.append(s);
//add number infront of existing result
if(s.charAt(0)>='a' && s.charAt(i)<='z')
{
sb=new StringBuilder(s.length()+1);
sb.append(Integer.toString(new Integer(1)));
sb.append(s);
//if first char of s is a number
}else
{
int i=0;
while(i<s.length())
{
if(s.charAt(i)>='a' && s.charAt(i)<='z')
{
break;
}
i++;
}
//get int value of the entire number
int v=Integer.parseInt(s.substring(0,i))+1;
String suffix=s.substring(i+1);
//append character value in front
sb=new StringBuilder(s.length());
sb.append(Integer.toString(new Integer(v)));
sb.append(suffix);
}

}
ls=newResults;
return ls;
}``````

• ``````public List<String>  f(String word) {
char[] cs = word.toCharArray();
int n = cs.length;
q.offer("");
for (int i = 0; i < n; i++) {
int qs = q.size();
for (int j = 0; j < qs; j++) {
String prefix = q.poll();
// for each prefix we have two options:
// 1. append the current char cs[i] to the prefix
q.offer(prefix + String.valueOf(cs[i]));
// 2. append 1 to the prefix
q.offer(prefix + "1");
}
}
List<String> result = new ArrayList<>(q.size());
while (!q.isEmpty()) {
char[] rs = q.poll().toCharArray();
// for each word we need to compact the sequences of ones into a number, ex w11d -> w2d, 1111 -> 4
StringBuilder sb = new StringBuilder();
int x = 0;
for (int i = 0; i < rs.length; i++) {
if (rs[i] == '1')
x++;
else {
if (x != 0) {
sb.append(x);
x = 0;
}
sb.append(rs[i]);
}
}
if (x != 0)
sb.append(x);
}
return result;
}``````

• Here's an easy iterative python version.

``````def abbrev(someWord):
n = len(someWord)
yield someWord
for nChars in range(1,n+1):
for start in range(n-nChars+1):
yield someWord[:start] + str(nChars) + someWord[start+nChars:]

for abb in abbrev('word'):
print abb
``````

• Here is my simple Java solution; I believe it's O(N^2). Please lemme know if I'm wrong!

``````public static List<String> solution(String s) {
for (int i = 0; i < s.length(); i++) {
for (int j = 1; j <= s.length() - i; j++) {
abbs.add(s.substring(0, i) + j + s.substring(j + i));
}
}
return abbs;
}
``````

• Javascript

``````const abbr = (w) => {
let f = (w) => {
if (w == "")
return [""];

let result = f(w.substr(1));
return result.map(x => w[0] + x)
.concat(
result.map(x => "1" + x)
);

};

return f(w).map(x => {
while (true) {
let m = /[1][1]+/.exec(x);
if (!m) return x;
x = x.replace(m[0], m[0].length);
}
});
};

``````

• @grodrigues3 The code could not generate `1o1d`, `1or1`, `w1r1` cases.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.