package com.interview.string;

/**
 * Date 07/08/2015
 * @author tushar_v_roy
 * 
 * Given a string like heads print all combination of abbreviation
 * Output should be
 * h1ads
 * h2ds
 * h3s
 * he1ds
 * he2s
 * hea1s
 */
public class WordAbbreviationCombination {
    public void shorten(char input[]){
        for(int i = 1; i < input.length-1; i++){
            for(int j=i; j < input.length-1; j++){
                for(int k=0; k < i; k++){
                    System.out.print(input[k]);
                }
                System.out.print(j-i+1);
                for(int k=j+1; k < input.length; k++){
                    System.out.print(input[k]);
                }
                System.out.println();
            }
        }
    }

    public static void main(String args[]) {
        WordAbbreviationCombination ssc = new WordAbbreviationCombination();
        ssc.shorten("heading".toCharArray());
    }
}

@@ -24,16 +24,37 @@
 tring;%0A%0A
+import java.util.*;%0A%0A
 /**%0A * D
@@ -62,17 +62,17 @@
 te 0
-7/08/2015
+4/17/2106
 %0A * 
@@ -83,161 +83,363 @@
 hor 
-t
+T
 ushar
-_v_r
+ R
 oy%0A *
- 
 %0A * 
-Given a string lik
+Write a function to generat
 e 
+t
 he
-ads print all combin
+ generalized abbrevi
 ation
+s
  of a
-bbreviation%0A * Output should be%0A * h1ads%0A * h2ds%0A * h3s%0A * he1ds%0A * he2s%0A * hea1s
+ word.%0A * Example:%0A * Given word = %22word%22, return the following list (order does not matter):%0A * %5B%22word%22, %221ord%22, %22w1rd%22, %22wo1d%22, %22wor1%22, %222rd%22, %22w2d%22, %22wo2%22, %221o1d%22, %221or1%22, %22w1r1%22, %221o2%22, %222r1%22, %223d%22, %22w3%22, %224%22%5D%0A *%0A * https://leetcode.com/problems/generalized-abbreviation/
 %0A */
@@ -482,16 +482,17 @@
 ation %7B%0A
+%0A
     publ
@@ -498,223 +498,419 @@
 lic 
-void shorten(char input%5B%5D)%7B%0A        for(int i = 1; i %3C input.length-1; i++)%7B%0A            for(int j=i; j %3C input.length-1; j++)%7B%0A                for(int k=0; k %3C i; k++)%7B%0A                    System.out.print(input%5Bk%5D
+List%3CString%3E generateAbbreviations(String word) %7B%0A        List%3CString%3E result = new ArrayList%3C%3E();%0A        generateAbbreviationsUtil(word, result, %22%22, 0, 0);%0A        return result;%0A    %7D%0A%0A    public void generateAbbreviationsUtil(String input, List%3CString%3E result, String current, int pos, int count) %7B%0A        if (input.length() == pos) %7B%0A            if (count %3E 0) %7B%0A                result.add(current + count
 );%0A 
@@ -912,37 +912,40 @@
 t);%0A            
-    %7D
+%7D else %7B
 %0A               
@@ -949,30 +949,26 @@
     
-System.out.print(j-i+1
+result.add(current
 );%0A 
@@ -982,50 +982,29 @@
     
+%7D%0A
     
-for(int k=j+1; k %3C input.length; k++)%7B
+        return;
 %0A   
@@ -1004,32 +1004,35 @@
 rn;%0A        
+%7D%0A%0A
         
     System.o
@@ -1023,119 +1023,196 @@
     
-    System.out.print(input%5Bk%5D);%0A                %7D%0A                System.out.println();%0A            %7D%0A        %7D
+generateAbbreviationsUtil(input, result, current, pos + 1, count + 1);%0A        generateAbbreviationsUtil(input, result, current + (count %3E 0 ? count : %22%22) + input.charAt(pos), pos + 1, 0);
 %0A   
@@ -1349,42 +1349,113 @@
     
-ssc.shorten(%22heading%22.toCharArray(
+List%3CString%3E result = ssc.generateAbbreviations(%22word%22);%0A        result.forEach(r -%3E System.out.println(r
 ));%0A

update word abbreviation solution